کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420388 683930 2009 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On graphs determining links with maximal number of components via medial construction
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On graphs determining links with maximal number of components via medial construction
چکیده انگلیسی

Let GG be a connected plane graph, D(G)D(G) be the corresponding link diagram via medial construction, and μ(D(G))μ(D(G)) be the number of components of the link diagram D(G)D(G). In this paper, we first provide an elementary proof that μ(D(G))≤n(G)+1μ(D(G))≤n(G)+1, where n(G)n(G) is the nullity of GG. Then we lay emphasis on the extremal graphs, i.e. the graphs with μ(D(G))=n(G)+1μ(D(G))=n(G)+1. An algorithm is given firstly to judge whether a graph is extremal or not, then we prove that all extremal graphs can be obtained from K1K1 by applying two graph operations repeatedly. We also present a dual characterization of extremal graphs and finally we provide a simple criterion on structures of bridgeless extremal graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 14, 28 July 2009, Pages 3099–3110
نویسندگان
, , ,