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 -

NotesEmbed ?

top

You must be logged in to post comments.