کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4649833 | 1342467 | 2009 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Boxicity of Halin graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A kk-dimensional box is the Cartesian product R1×R2×⋯×RkR1×R2×⋯×Rk where each RiRi is a closed interval on the real line. The boxicity of a graph GG, denoted as box(G) is the minimum integer kk such that GG is the intersection graph of a collection of kk-dimensional boxes. Halin graphs are the graphs formed by taking a tree with no degree 2 vertex and then connecting its leaves to form a cycle in such a way that the graph has a planar embedding. We prove that if GG is a Halin graph that is not isomorphic to K4K4, then box(G)=2. In fact, we prove the stronger result that if GG is a planar graph formed by connecting the leaves of any tree in a simple cycle, then box(G)=2 unless GG is isomorphic to K4K4 (in which case its boxicity is 1).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 10, 28 May 2009, Pages 3233–3237
Journal: Discrete Mathematics - Volume 309, Issue 10, 28 May 2009, Pages 3233–3237
نویسندگان
L. Sunil Chandran, Mathew C. Francis, Santhosh Suresh,