graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a Ptolemaic graph is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

whose

shortest path In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between tw ...

distances obey

Ptolemy's inequality In Euclidean geometry, Ptolemy's inequality relates the six distances determined by four points in the plane or in a higher-dimensional space. It states that, for any four points , , , and , the following inequality holds: :\overline\cdot \overline ...

, which in turn was named after the

Greek Greek may refer to: Greece Anything of, from, or related to Greece, a country in Southern Europe: *Greeks, an ethnic group. *Greek language, a branch of the Indo-European language family. **Proto-Greek language, the assumed last common ancestor ...

astronomer An astronomer is a scientist in the field of astronomy who focuses their studies on a specific question or field outside the scope of Earth. They observe astronomical objects such as stars, planets, natural satellite, moons, comets and galaxy, g ...

and

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

Ptolemy Claudius Ptolemy (; grc-gre, Πτολεμαῖος, ; la, Claudius Ptolemaeus; AD) was a mathematician, astronomer, astrologer, geographer, and music theorist, who wrote about a dozen scientific treatises, three of which were of importanc ...

. The Ptolemaic graphs are exactly the graphs that are both chordal and distance-hereditary; they include the

block graph In graph theory, a branch of combinatorial mathematics, a block graph or clique tree. is a type of undirected graph in which every biconnected component (block) is a clique. Block graphs are sometimes erroneously called Husimi trees (after Kô ...

s and are a subclass of the

perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfec ...

Characterization

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

distances obey

: for every four vertices , , , and , the inequality holds.. For instance, the

gem graph A gemstone (also called a fine gem, jewel, precious stone, or semiprecious stone) is a piece of mineral crystal which, in cut and polished form, is used to make jewellery, jewelry or other adornments. However, certain Rock (geology), rocks (suc ...

(3-fan) in the illustration is not Ptolemaic, because in this graph , greater than . *For every two overlapping

maximal clique In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is comple ...

s, the intersection of the two cliques is a separator that splits the differences of the two cliques.. In the illustration of the gem graph, this is not true: cliques and are not separated by their intersection, , because there is an edge that connects the cliques but avoids the intersection. *Every -vertex cycle has at least diagonals. *The graph is both chordal (every cycle of length greater than three has a diagonal) and distance-hereditary (every connected

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

has the same distances as the whole graph). The gem shown is chordal but not distance-hereditary: in the subgraph induced by , the distance from to is 3, greater than the distance between the same vertices in the whole graph. Because both chordal and distance-hereditary graphs are

s, so are the Ptolemaic graphs. *The graph is chordal and does not contain an induced gem, a graph formed by adding two non-crossing diagonals to a pentagon.. *The graph is distance-hereditary and does not contain an induced 4-cycle. *The graph can be constructed from a single vertex by a sequence of operations that add a new degree-one (pendant) vertex, or duplicate (twin) an existing vertex, with the exception that a twin operation in which the new duplicate vertex is not adjacent to its twin (false twins) can only be applied when the neighbors of the twins form a clique. These three operations without the exception form all distance-hereditary graph. To form all Ptolemaic graphs, it is not enough to use pendant vertices and true twins; the exceptional case of false twins is sometimes also required. *The

Hasse diagram In order theory, a Hasse diagram (; ) is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set ''(S, ≤)'' one represents ea ...

of the subset relation on nonempty intersections of maximal cliques forms an

oriented tree In mathematics, and more specifically in graph theory, a polytree (also called directed tree, oriented tree; . or singly connected network.) is a directed acyclic graph whose underlying undirected graph is a tree. In other words, if we replace its ...

.. *The convex subsets of vertices (subsets that contain every shortest path between two vertices in the subset) form a

convex geometry In mathematics, convex geometry is the branch of geometry studying convex sets, mainly in Euclidean space. Convex sets occur naturally in many areas: computational geometry, convex analysis, discrete geometry, functional analysis, geometry of numbe ...

. That is, every convex set can be reached from the whole vertex set by repeatedly removing an extreme vertex, one that does not belong to any shortest path between the remaining vertices. In the gem, the convex set cannot be reached in this way, because neither nor is extreme.

Computational complexity

Based on the characterization by oriented trees, Ptolemaic graphs can be recognized in

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

Enumeration

The

generating function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...

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

n=1,2,3,\dots

, has been found to be :1, 1, 4, 35, 481, 9042, 216077, 6271057, 214248958, 8424002973, 374708368981, 18604033129948, 1019915376831963, ...

References

{{reflist Graph families Perfect graphs Intersection classes of graphs