Boxicity of Halin graphs |
| |
Authors: | L. Sunil Chandran Mathew C. Francis |
| |
Affiliation: | a Department of Computer Science and Automation, Indian Institute of Science, Bangalore-560012, India b Department of Mechanical Engineering, Indian Institute of Technology Madras, Chennai-600036, India |
| |
Abstract: | A k-dimensional box is the Cartesian product R1×R2×?×Rk where each Ri is a closed interval on the real line. The boxicity of a graph G, denoted as is the minimum integer k such that G is the intersection graph of a collection of k-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 G is a Halin graph that is not isomorphic to K4, then . In fact, we prove the stronger result that if G is a planar graph formed by connecting the leaves of any tree in a simple cycle, then unless G is isomorphic to K4 (in which case its boxicity is 1). |
| |
Keywords: | Halin graphs Boxicity Intersection graphs Planar graphs |
本文献已被 ScienceDirect 等数据库收录! |
|