Boxicity of Leaf Powers
| dc.creator | Chandran, L. Sunil | |
| dc.creator | Francis, Mathew C. | |
| dc.creator | Mathew, Rogers | |
| dc.date | 2009-02-20 | |
| dc.date.accessioned | 2026-07-07T12:45:00Z | |
| dc.date.available | 2026-07-07T12:45:00Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/0902.3551 | |
| dc.identifier | http://arxiv.org/abs/0902.3551 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/220962 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C62 (Primary) 05C05 (Secondary) | |
| dc.title | Boxicity of Leaf Powers | |
| dc.type | text |