Ptolemaic Graphs and Interval Graphs Are Leaf Powers
| 详细信息 | 推荐本文 | |
- 作者：Andreas Brandst盲dt ; Christian Hundt
- 关键词：Leaf powers ; leaf roots ; strongly chordal graphs ; ptolemaic graphs ; graph powers ; graph class inclusions ; (unit) interval graphs ; clique ; width
- 刊名：Lecture Notes in Computer Science
- 出版时间：2008
- 出版年：2008
- 期刊代码：99_0302-9743
- 类别：cp
- 卷：4957
- 期：1
- 页码：479-491
- 数据来源：sp
摘要
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.