Boxicity of Halin graphs

DOI10.1016/J.DISC.2008.09.037MaRDI QIDQ1025946zbMATH OpenOpenAlexFDO

Authors L. Sunil Chandran, Mathew C. Francis, Santhosh Suresh

Publication date 23 June 2009

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0711.1417

zbMATH Keywords

intersection graphsplanar graphsboxicityHalin graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75)

Abstract: 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).

Recommendations

• Boxicity of graphs on surfaces
• Boxicity and maximum degree
• Grid intersection graphs and boxicity
• Boxicity and topological invariants
• Boxicity and treewidth

Cites work

• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• scientific article; zbMATH DE number 3346402 (Why is no real title available?)
• A special planar satisfiability problem and a consequence of its NP- completeness
• Boxicity and maximum degree
• Boxicity and treewidth
• Boxicity of series-parallel graphs
• Characterization of the graphs with boxicity \(\leq 2\)
• Dominating cycles in Halin graphs
• Geometric representation of graphs in low dimension using axis parallel boxes
• Halin graphs and the travelling salesman problem
• Interval representations of planar graphs
• Lengths of cycles in halin graphs
• On a Family of Planar Bicritical Graphs
• The Complexity of the Partial Order Dimension Problem
• When the cartesian product of directed cycles is Hamiltonian

Cited in

(8)

• Boxicity of leaf powers
• Boxicity of circular arc graphs
• scientific article; zbMATH DE number 5214885 (Why is no real title available?)
• Listing all spanning trees in Halin graphs -- sequential and parallel view
• Boxicity of graphs on surfaces
• scientific article; zbMATH DE number 1835115 (Why is no real title available?)
• Periodic solutions of an asymptotically linear Dirac equation
• Boxicity and topological invariants

This page was built for publication: Boxicity of Halin graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1025946)