Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

End Simplicial Vertices in Path Graphs

100%

Gutierrez M., Tondato S. B.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 2

393-408

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.

Asteroidal Quadruples in non Rooted Path Graphs

81%

Gutierrez M., Lévêque B., Tondato S. B.

Discussiones Mathematicae Graph Theory

2015

tom 35

nr 4

603-614

A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted path graph is the intersection graph of a family of directed subpaths of a rooted tree. Rooted path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted path graphs. For this purpose, we are studying in this paper directed path graphs that are non rooted path graphs. We prove that such graphs always contain an asteroidal quadruple.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Gutierrez M.

2 Tondato S. B.

1 Lévêque B.

1 2016

1 2015

Wyniki wyszukiwania

End Simplicial Vertices in Path Graphs

Asteroidal Quadruples in non Rooted Path Graphs