Boxicity of leaf powers

DOI10.1007/S00373-010-0962-5MaRDI QIDQ659669zbMATH OpenOpenAlexFDO

Authors L. Sunil Chandran, Mathew C. Francis, Rogers Mathew

Publication date 24 January 2012

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

interval graphsboxicitystrongly chordal graphsleaf powerstree powers

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: The boxicity of a graph G, denoted as box(G) is defined as the minimum integer t such that G is an intersection graph of axis-parallel t-dimensional boxes. A graph G is a k-leaf power if there exists a tree T such that the leaves of the tree correspond to the vertices of G and two vertices in G are adjacent if and only if their corresponding leaves in T are at a distance of at most k. Leaf powers are a subclass of strongly chordal graphs and are used in the construction of phylogenetic trees in evolutionary biology. We show that for a k-leaf power G, box(G)leq k-1. We also show the tightness of this bound by constructing a k-leaf power with boxicity equal to k-1. This result implies that there exists strongly chordal graphs with arbitrarily high boxicity which is somewhat counterintuitive.

Recommendations

• Rooted directed path graphs are leaf powers
• Ptolemaic Graphs and Interval Graphs Are Leaf Powers
• On strongly chordal graphs that are not leaf powers
• Characterising \((k,\ell )\)-leaf powers
• Boxicity of Halin graphs

Cites work

• scientific article; zbMATH DE number 4077265 (Why is no real title available?)
• scientific article; zbMATH DE number 165077 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• A characterization of strongly chordal graphs
• Boxicity and maximum degree
• Boxicity and treewidth
• Boxicity of Halin graphs
• Boxicity of circular arc graphs
• Boxicity of series-parallel graphs
• Characterizations of strongly chordal graphs
• Chordal bipartite, strongly chordal, and strongly chordal bipartite graphs
• Closest 4-leaf power is fixed-parameter tractable
• Computing the boxicity of a graph by covering its complement by cointerval graphs
• Geometric representation of graphs in low dimension using axis parallel boxes
• Interval representations of planar graphs
• On (k,ℓ)-Leaf Powers
• On graph powers for leaf-labeled trees
• Representation of a finite graph by a set of intervals on the real line
• Strictly chordal graphs are leaf powers
• Strong clique trees, neighborhood trees, and strongly chordal graphs
• Structure and linear time recognition of 3-leaf powers
• Structure and linear-time recognition of 4-leaf powers

Cited in

(3)

• Exact leaf powers
• Boxicity of line graphs
• Separability, boxicity, and partial orders

This page was built for publication: Boxicity of leaf powers

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