Boxicity of Halin Graphs
| dc.creator | Chandran, L. Sunil | |
| dc.creator | Francis, Mathew C. | |
| dc.creator | Suresh, Santhosh | |
| dc.date | 2007-11-09 | |
| dc.date.accessioned | 2026-07-07T08:41:51Z | |
| dc.date.available | 2026-07-07T08:41:51Z | |
| dc.description | A k-dimensional box is the Cartesian product R_1 x R_2 x ... x R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G) 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 K_4, then box(G)=2. 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 box(G)=2 unless G is isomorphic to K_4 (in which case its boxicity is 1). | |
| dc.description | 9 pages | |
| dc.identifier | https://arxiv.org/abs/0711.1417 | |
| dc.identifier | http://arxiv.org/abs/0711.1417 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/141806 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C62 | |
| dc.title | Boxicity of Halin Graphs | |
| dc.type | text |