Boxicity of Leaf Powers
Data(s) |
01/01/2011
|
---|---|
Resumo |
The boxicity of a graph G, denoted as boxi(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, boxi(G) a parts per thousand currency sign 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. |
Formato |
application/pdf |
Identificador |
http://eprints.iisc.ernet.in/35017/1/Boxicity.pdf Chandran, Sunil L and Francis, Mathew C and Mathew, Rogers (2011) Boxicity of Leaf Powers. In: Graphs and Combinatorics, 27 (1). pp. 61-72. |
Publicador |
Springer |
Relação |
http://www.springerlink.com/content/c642jv44l84118u1/ http://eprints.iisc.ernet.in/35017/ |
Palavras-Chave | #Computer Science & Automation (Formerly, School of Automation) |
Tipo |
Journal Article PeerReviewed |