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 and are a subclass of the perfect graphs.

Characterization

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.

Enumeration

The generating function for Ptolemaic graphs can be described symbolically, allowing the rapid calculation of the numbers of these graphs. Based on this method, the number of Ptolemaic graphs with labeled vertices, for, has been found to be