Ptolemaic Graphs and Interval Graphs Are Leaf Powers
Motivated by the problem of reconstructing evolutionary history, Nishimura, Radge and Thilikos introduced the notion of k-leaf powers as the class of graphs G = (V,E) which have a k-leaf root, i.e., a tree T with leaf set V where xy ∈ E if and only if the
- PDF / 426,391 Bytes
- 13 Pages / 430 x 660 pts Page_size
- 76 Downloads / 156 Views
bstract. Motivated by the problem of reconstructing evolutionary history, Nishimura, Radge and Thilikos introduced the notion of k-leaf powers as the class of graphs G = (V, E) which have a k-leaf root, i.e., a tree T with leaf set V where xy ∈ E if and only if the T -distance between x and y is at most k. It is known that leaf powers are strongly chordal (i.e., sun-free chordal) graphs. Despite extensive research, the problem of recognizing leaf powers, i.e., to decide for a given graph G whether it is a k-leaf power for some k, remains open. Much less is known on the complexity of finding the leaf rank of G, i.e., to determine the minimum number k such that G is a k-leaf power. A result by Bibelnieks and Dearing implies that not every strongly chordal graph is a leaf power. Recently, Kennedy, Lin and Yan have shown that dart- and gem-free chordal graphs are 4-leaf powers. We generalize their result and show that ptolemaic (i.e., gem-free chordal) graphs are leaf powers. Moreover, ptolemaic graphs have unbounded leaf rank. Furthermore, we show that interval graphs are leaf powers which implies that leaf powers have unbounded clique-width. Finally, we characterize unit interval graphs as those leaf powers having a caterpillar leaf root. Keywords and Classification: Leaf powers; leaf roots; strongly chordal graphs; ptolemaic graphs; graph powers; graph class inclusions; (unit) interval graphs; clique-width.
1
Introduction
Motivated by the problem of reconstructing evolutionary history, and by the notion of k-th phylogenetic power and k-root phylogeny of a graph G introduced by Lin, Kearney and Jiang [23] (see also [10]), Nishimura, Ragde and Thilikos [26] introduced the following notion: A tree T = (VT , ET ) is a k-leaf root of a finite undirected graph G = (V, E) if the set of leaves of T is V and for any two vertices x, y ∈ V , xy ∈ E if and only if the distance of x and y in T is at most k. Graph G is a k-leaf power if it has a k-leaf root. In general, G is a leaf power if it is a k-leaf power for some k, and a k-leaf root T of G is also called leaf root. The vertex set VT of T consists of leaves and internal nodes. Note that internal nodes may have degree two; in phylogenetic roots, internal nodes have degree larger than two but edges are weighted. The two models are equivalent because E.S. Laber et al. (Eds.): LATIN 2008, LNCS 4957, pp. 479–491, 2008. c Springer-Verlag Berlin Heidelberg 2008
480
A. Brandst¨ adt and C. Hundt
a path of degree two nodes can be contracted to one edge with the length of the corresponding path as its weight. For a leaf power G, its leaf rank lr(G) is the smallest k such that G has a k-leaf root. For a class G of leaf powers, let lr(G) be the maximum lr(G) over all G ∈ G, and infinite if it is unbounded. Obviously, a graph G is a 2-leaf power if and only if it is the disjoint union of cliques, i.e., G is P3 -free (where P3 denotes the path with three vertices and two edges). The 3-leaf powers are exactly the bull-, dart-, and gem-free chordal graphs [14] (see Figure 1 for bull, da
Data Loading...
