Geodesic
End Simplicial Vertices in Path Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 393-408.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: chordal graphs, clique trees, path graphs 
@article{DMGT_2016_36_2_a10,
     author = {Gutierrez, Marisa and Tondato, Silvia B.},
     title = {End {Simplicial} {Vertices} in {Path} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {393--408},
     publisher = {mathdoc},
     volume = {36},
     number = {2},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a10/}
}
TY  - JOUR
AU  - Gutierrez, Marisa
AU  - Tondato, Silvia B.
TI  - End Simplicial Vertices in Path Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 393
EP  - 408
VL  - 36
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a10/
LA  - en
ID  - DMGT_2016_36_2_a10
ER  - 
%0 Journal Article
%A Gutierrez, Marisa
%A Tondato, Silvia B.
%T End Simplicial Vertices in Path Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 393-408
%V 36
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a10/
%G en
%F DMGT_2016_36_2_a10
Gutierrez, Marisa; Tondato, Silvia B. End Simplicial Vertices in Path Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 393-408. http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a10/

[1] J.R.S. Blair and B.W. Peyton, On finding minimum-diameter clique trees, Nordic J. Comput. 1 (1994) 173-201.

[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

[3] J. Gimbel, End vertices in interval graphs, Discrete Appl. Math. 21 (1988) 257-259. doi:10.1016/0166-218X(88)90071-6

[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

[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

[6] Y. Shibata, On the tree representation of chordal graphs, J. Graph Theory 12 (1988) 421-428. doi:10.1002/jgt.3190120313

[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