TOPICS

# Ptolemaic Graph

Define

 (1) (2) (3)

where , , , and are vertices of a graph and is the graph distance between vertices and . Then a connected Ptolemaic graph is a graph such that a weak form of the triangle inequality

 (4) (5) (6)

holds for any four vertices (Kay and Chartrand 1965, Howorka 1981).

The numbers of connected Ptolemaic graphs on , 2, ... vertices are 1, 1, 2, 5, 14, 47, 170, 676, 2834, 12471, 56675, 264906, ... (OEIS A287888).

The definition can be extended to disconnected graphs by allowing 4-tuples of points in each connected component to satisfy these conditions separately (Bahrani and Lumbroso 2016).

A connected graph is Ptolemaic iff is it distance-heritary and chordal (Howorka 1981, Bahrani and Lumbroso 2016). Ptolemaic graphs are perfect.

Classes of graphs that are Ptolemaic include block graphs.

Chordal Graph, Distance-Hereditary Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Bahrani, M. and Lumbroso, J. "Enumerations, Forbidden Subgraph Characterizations, and the Split-Decomposition." 4 Aug 2016. https://arxiv.org/abs/1608.01465.Howorka, E. "A Characterization of Ptolemaic Graphs." J. Graph Th. 5, 323-331, 1981.Kay, D. C. and Chartrand, G. "A Characterization of Certain Ptolemaic Graphs." Canad. J. Math. 17, 342-346, 1965.Sloane, N. J. A. Sequence A287888 in "The On-Line Encyclopedia of Integer Sequences."

## Cite this as:

Weisstein, Eric W. "Ptolemaic Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PtolemaicGraph.html