✦ LIBER ✦

Metric characterizations of proper interval graphs and tree-clique graphs

✍ Scribed by Gutierrez, M.; Oubi�a, L.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 393 KB
Volume: 21
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199602)21:2<199::aid-jgt9>3.0.co;2-m

No coin nor oath required. For personal study only.

✦ Synopsis

A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When Tis a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real line such that no interval contains another. W e present here metric characterizations of proper interval graphs and extend them to tree-clique graphs. This IS done by demonstrating "local" properties of treeclique graphs with respect to the subgraphs induced by paths of a compatible tree.