Premium
Metric characterizations of proper interval graphs and tree‐clique graphs
Author(s) -
Gutierrez M.,
Oubiña L.
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199602)21:2<199::aid-jgt9>3.0.co;2-m
Subject(s) - combinatorics , block graph , mathematics , interval graph , split graph , chordal graph , discrete mathematics , clique graph , tree (set theory) , indifference graph , treewidth , clique sum , clique , pathwidth , line graph , graph , graph power , 1 planar graph
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 T is 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. We present here metric characterizations of proper interval graphs and extend them to tree‐clique graphs. This is done by demonstrating “local” properties of tree‐clique graphs with respect to the subgraphs induced by paths of a compatible tree. © 1996 John Wiley & Sons, Inc.