Boxicity of Leaf Powers

Details Boxicity of Leaf Powers Boxicity of Leaf Powers

2009-02-20

arxiv.org/abs/0902.3551v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Boxicity of Leaf Powers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Boxicity of Leaf Powers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boxicity of Leaf Powers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-671060