Metric characterizations of proper interval graphs and tree-clique graphs : Notas de Matemática, 54
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...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Publicacion seriada |
| Lenguaje: | Inglés |
| Publicado: |
1994
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/170672 |
| Aporte de: |
| Sumario: | 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. |
|---|