End simplicial vertices in path graphs
A graph is a path graph if there is a tree, called UV-model, whose vertices are the maximal cliques of the graph and for each vertex x of the graph the set of maximal cliques that contains it induces a path in the tree. A graph is an interval graph if there is a UV-model that is a path, called an in...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Articulo |
| Lenguaje: | Inglés |
| Publicado: |
2016
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/87295 |
| Aporte de: |
| Sumario: | A graph is a path graph if there is a tree, called UV-model, whose vertices are the maximal cliques of the graph and for each vertex x of the graph the set of maximal cliques that contains it induces a path in the tree. A graph is an interval graph if there is a UV-model that is a path, called an interval model. Gimbel [3] characterized those vertices in interval graphs for which there is some interval model where the interval corresponding to those vertices is an end interval. In this work, we give a characterization of those simplicial vertices x in path graphs for which there is some t/V-model where the maximal clique containing x is a leaf in this UV-model. |
|---|