Ptolemaic graph

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: Based on the characterization by oriented trees, Ptolemaic graphs can be recognized in linear time.

[6] The generating function for Ptolemaic graphs can be described symbolically, allowing the fast calculation of the numbers of these graphs.

Based on this method, the number of Ptolemaic graphs with n labeled vertices, for

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.