《Boxicity of Leaf Powers》.pdfVIP

Boxicity of Leaf Powers L. Sunil Chandran, Mathew C. Francis, and Rogers Mathew Department of Computer Science and Automation, Indian Institute of Science, 9 Bangalore – 560012, India. 0 {sunil,mathew,rogers}@csa.iisc.ernet.in 0 2 b e Abstract. The boxicity of a graph G, denoted as box(G) is defined F 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 0 2 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 O chordal graphs and are used in the construction of phylogenetic trees C in evolutionary biology. 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 h power with boxicity equal to k − 1. This result implies that there exists t a strongly chordal graphs with arbitrarily high boxicity which is somewhat m counterintuitive. [ Key words: Boxicity, leaf powers, tree powers, strongly chordal graphs, interval graphs. 1 v 1 5 1 Introduction 5 3 A