Back to Search
Start Over
Boxicity of Halin graphs
- Source :
-
Discrete Mathematics . May2009, Vol. 309 Issue 10, p3233-3237. 5p. - Publication Year :
- 2009
-
Abstract
- Abstract: A -dimensional box is the Cartesian product where each is a closed interval on the real line. The boxicity of a graph , denoted as is the minimum integer such that is the intersection graph of a collection of -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 is a Halin graph that is not isomorphic to , then . In fact, we prove the stronger result that if is a planar graph formed by connecting the leaves of any tree in a simple cycle, then unless is isomorphic to (in which case its boxicity is 1). [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 309
- Issue :
- 10
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 38806545
- Full Text :
- https://doi.org/10.1016/j.disc.2008.09.037