Header menu link for other important links
X
Boxicity of Leaf Powers
L.S. Chandran, M.C. Francis,
Published in
2011
Volume: 27
   
Issue: 1
Pages: 61 - 72
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 used in the construction of phylogenetic trees in evolutionary biology and have been studied in many recent papers. We show that for a k-leaf power G, box(G) ≤ 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 exist strongly chordal graphs with arbitrarily high boxicity which is somewhat counterintuitive. © 2010 Springer.
About the journal
JournalGraphs and Combinatorics
ISSN09110119