TOPICS
Search

Ptolemaic Graph


Define

a=d(u,v)d(w,x)
(1)
b=d(u,w)d(v,x)
(2)
c=d(u,x)d(v,w),
(3)

where u, v, w, and x are vertices of a graph and d(i,j) is the graph distance between vertices i and j. Then a connected Ptolemaic graph is a graph G such that a weak form of the triangle inequality

a+b>=c
(4)
b+c>=a
(5)
c+a>=b
(6)

holds for any four vertices (u,v,w,x) (Kay and Chartrand 1965, Howorka 1981).

PtolemaicGraphs

The numbers of connected Ptolemaic graphs on n=1, 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.


See also

Chordal Graph, Distance-Hereditary Graph

Explore with Wolfram|Alpha

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

Subject classifications