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

Abstract

top
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.

How to cite

top

Marisa 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. [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. [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. [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. [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. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.