Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649833 | Discrete Mathematics | 2009 | 5 Pages |
Abstract
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).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
L. Sunil Chandran, Mathew C. Francis, Santhosh Suresh,