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

چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 157, Issue 14, 28 July 2009, Pages 3099–3110
نویسندگان
Xian’an Jin, Fengming Dong, Eng Guan Tay,