# End Simplicial Vertices in Path Graphs

Marisa Gutierrez; Silvia B. Tondato

Discussiones Mathematicae Graph Theory (2016)

- Volume: 36, Issue: 2, page 393-408
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMarisa Gutierrez, and Silvia B. Tondato. "End Simplicial Vertices in Path Graphs." Discussiones Mathematicae Graph Theory 36.2 (2016): 393-408. <http://eudml.org/doc/277126>.

@article{MarisaGutierrez2016,

abstract = {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 UV -model where the maximal clique containing x is a leaf in this UV -model.},

author = {Marisa Gutierrez, Silvia B. Tondato},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {chordal graphs; clique trees; path graphs},

language = {eng},

number = {2},

pages = {393-408},

title = {End Simplicial Vertices in Path Graphs},

url = {http://eudml.org/doc/277126},

volume = {36},

year = {2016},

}

TY - JOUR

AU - Marisa Gutierrez

AU - Silvia B. Tondato

TI - End Simplicial Vertices in Path Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2016

VL - 36

IS - 2

SP - 393

EP - 408

AB - 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 UV -model where the maximal clique containing x is a leaf in this UV -model.

LA - eng

KW - chordal graphs; clique trees; path graphs

UR - http://eudml.org/doc/277126

ER -

## References

top- [1] J.R.S. Blair and B.W. Peyton, On finding minimum-diameter clique trees, Nordic J. Comput. 1 (1994) 173-201. Zbl0819.68085
- [2] F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Combin. Theory Ser. B 16 (1974) 47-56. doi:10.1016/0095-8956(74)90094-X[Crossref]
- [3] J. Gimbel, End vertices in interval graphs, Discrete Appl. Math. 21 (1988) 257-259. doi:10.1016/0166-218X(88)90071-6[Crossref] Zbl0671.05035
- [4] B. Lévêque, F. Maffray and M. Preissmann, Characterizing path graphs by forbidden induced subgraphs, J. Graph Theory 62 (2009) 369-384. doi:10.1002/jgt.20407[Crossref] Zbl1221.05220
- [5] C. Monma and V. Wei, Intersection graphs of paths in a tree, J. Combin. Theory Ser. B 41 (1986) 141-181. doi:10.1016/0095-8956(86)90042-0[Crossref]
- [6] Y. Shibata, On the tree representation of chordal graphs, J. Graph Theory 12 (1988) 421-428. doi:10.1002/jgt.3190120313[Crossref] Zbl0654.05022
- [7] J.R.Walter, Representations of chordal graphs as subtrees of a tree, J. Graph Theory 2 (1978) 265-267. doi:10.1002/jgt.3190020311[Crossref] Zbl0441.05022

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.