Ptolemaic graph

A Ptolemaic graph
The gem graph or 3-fan is not Ptolemaic.
A block graph, a special case of a Ptolemaic graph
Three operations by which any distance-hereditary graph can be constructed. For Ptolemaic graphs, the neighbors of false twins are restricted to form a clique, preventing the construction of the 4-cycle shown here.

In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs that are both chordal and distance-hereditary; they include the block graphs[1] and are a subclass of the perfect graphs.


A graph is Ptolemaic if and only if it obeys any of the following equivalent conditions:

Computational complexity

Based on the characterization by oriented trees, Ptolemaic graphs can be recognized in linear time.[6]


  1. 1 2 Kay, David C.; Chartrand, Gary (1965), "A characterization of certain ptolemaic graphs", Canadian Journal of Mathematics, 17: 342–346, doi:10.4153/CJM-1965-034-0, MR 0175113.
  2. 1 2 3 Howorka, Edward (1981), "A characterization of Ptolemaic graphs", Journal of Graph Theory, 5 (3): 323–331, doi:10.1002/jgt.3190050314, MR 625074.
  3. 1 2 "Graphclass: ptolemaic", Information System on Graph Classes and their Inclusions, retrieved 2016-06-05.
  4. McKee, Terry A. (2010), "Clique graph representations of Ptolemaic graphs", Discussiones Mathematicae Graph Theory, 30 (4): 651–661, doi:10.7151/dmgt.1520, MR 2761626.
  5. Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986), "Distance-hereditary graphs", Journal of Combinatorial Theory, Series B, 41 (2): 182–208, doi:10.1016/0095-8956(86)90043-2, MR 859310.
  6. 1 2 Uehara, Ryuhei; Uno, Yushi (2009), "Laminar structure of Ptolemaic graphs with applications", Discrete Applied Mathematics, 157 (7): 1533–1543, doi:10.1016/j.dam.2008.09.006, MR 2510233.
  7. Farber, Martin; Jamison, Robert E. (1986), "Convexity in graphs and hypergraphs", SIAM Journal on Algebraic and Discrete Methods, 7 (3): 433–444, doi:10.1137/0607049, MR 844046.
This article is issued from Wikipedia - version of the 6/7/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.