- Tytuł:
- Clique graph representations of ptolemaic graphs
- Autorzy:
- McKee, Terry
- Powiązania:
- https://bibliotekanauki.pl/articles/744102.pdf
- Data publikacji:
- 2010
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
Ptolemaic graph
clique graph
chordal graph
clique tree
graph representation - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2010, 30, 4; 651-661
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł