Clique graph representations of ptolemaic graphs

Terry A. Mckee

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 4, page 651-661
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Terry A. Mckee. "Clique graph representations of ptolemaic graphs." Discussiones Mathematicae Graph Theory 30.4 (2010): 651-661. <http://eudml.org/doc/271064>.

@article{TerryA2010,
abstract = {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.},
author = {Terry A. Mckee},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Ptolemaic graph; clique graph; chordal graph; clique tree; graph representation},
language = {eng},
number = {4},
pages = {651-661},
title = {Clique graph representations of ptolemaic graphs},
url = {http://eudml.org/doc/271064},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Terry A. Mckee
TI - Clique graph representations of ptolemaic graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 4
SP - 651
EP - 661
AB - 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.
LA - eng
KW - Ptolemaic graph; clique graph; chordal graph; clique tree; graph representation
UR - http://eudml.org/doc/271064
ER -

References

top
  1. [1] H.-J. Bandelt and E. Prisner, Clique graphs and Helly graphs, J. Combin. Theory (B) 51 (1991) 34-45, doi: 10.1016/0095-8956(91)90004-4. Zbl0726.05060
  2. [2] B.-L. Chen and K.-W. Lih, Diameters of iterated clique graphs of chordal graphs, J. Graph Theory 14 (1990) 391-396, doi: 10.1002/jgt.3190140311. Zbl0726.05059
  3. [3] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey, Society for Industrial and Applied Mathematics (Philadelphia, 1999). 
  4. [4] E. Howorka, A characterization of ptolemaic graphs, J. Graph Theory 5 (1981) 323-331, doi: 10.1002/jgt.3190050314. Zbl0437.05046
  5. [5] T.A. McKee, Maximal connected cographs in distance-hereditary graphs, Utilitas Math. 57 (2000) 73-80. Zbl0953.05024
  6. [6] T.A. McKee and F.R. McMorris, Topics in Intersection Graph Theory, Society for Industrial and Applied Mathematics (Philadelphia, 1999). Zbl0945.05003
  7. [7] F. Nicolai, A hypertree characterization of distance-hereditary graphs, Tech. Report Gerhard-Mercator-Universität Gesamthochschule (Duisburg SM-DU-255, 1994). 
  8. [8] E. Prisner, Graph Dynamics, Pitman Research Notes in Mathematics Series #338 (Longman, Harlow, 1995). 
  9. [9] J.L. Szwarcfiter, A survey on clique graphs, in: Recent advances in algorithms and combinatorics, pp. 109-136, CMS Books Math./Ouvrages Math. SMC 11 (Springer, New York, 2003). Zbl1027.05071

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.