Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Ptolemaic graph

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Clique graph representations of ptolemaic graphs

100%

McKee T.

Discussiones Mathematicae Graph Theory

2010

tom 30

nr 4

651-661

A graph is ptolemaic if and only if it is both chordal and distance-hereditary. Thus, a ptolemaic graph G has two kinds of intersection graph representations: one from being chordal, and the other from being distance-hereditary. The first of these, called a clique tree representation, is easily generated from the clique graph of G (the intersection graph of the maximal complete subgraphs of G). The second intersection graph representation can also be generated from the clique graph, as a very special case of the main result: The maximal Pₙ-free connected induced subgraphs of the p-clique graph of a ptolemaic graph G correspond in a natural way to the maximal $P_{n+1}$-free induced subgraphs of G in which every two nonadjacent vertices are connected by at least p internally disjoint paths.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 McKee T.

1 2010

Wyniki wyszukiwania

Clique graph representations of ptolemaic graphs