Ptolemaic graph

Last updated August 19, 2023

The gem graph or 3-fan is not Ptolemaic. Graph00001.svg — The gem graph or 3-fan is not Ptolemaic.

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.

Characterization

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

The shortest path distances obey Ptolemy's inequality: for every four vertices $u$ , $v$ , $w$ , and $x$ , the inequality $d (u, v) d (w, x) + d (u, x) d (v, w) \geq d (u, w) d (v, x)$ holds.^[1] For instance, the gem graph (3-fan) in the illustration is not Ptolemaic, because in this graph $d (u, w) d (v, x) = 4$ , greater than $d (u, v) d (w, x) + d (u, x) d (v, w) = 3$ .
For every two overlapping maximal cliques, the intersection of the two cliques is a separator that splits the differences of the two cliques.^[2] In the illustration of the gem graph, this is not true: cliques $uvy$ and $wxy$ are not separated by their intersection, $y$ , because there is an edge $vw$ that connects the cliques but avoids the intersection.
Every $k$ -vertex cycle has at least $3(k - 3)/2$ diagonals.^[2]
The graph is both chordal (every cycle of length greater than three has a diagonal) and distance-hereditary (every connected induced subgraph has the same distances as the whole graph).^[2] The gem shown is chordal but not distance-hereditary: in the subgraph induced by $uvwx$ , the distance from $u$ to $x$ is 3, greater than the distance between the same vertices in the whole graph. Because both chordal and distance-hereditary graphs are perfect graphs, so are the Ptolemaic graphs.^[3]
The graph is chordal and does not contain an induced gem, a graph formed by adding two non-crossing diagonals to a pentagon.^[3]
The graph is distance-hereditary and does not contain an induced 4-cycle.^[4]
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.^[5]
The Hasse diagram of the subset relation on nonempty intersections of maximal cliques forms an oriented tree.^[6]
The convex subsets of vertices (subsets that contain every shortest path between two vertices in the subset) form a convex geometry. 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.^[7] In the gem, the convex set $uxy$ cannot be reached in this way, because neither $v$ nor $w$ is extreme.

Computational complexity

Based on the characterization by oriented trees, Ptolemaic graphs can be recognized in linear time.^[6]

Enumeration

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 $n=1,2,3,\dots$ , has been found to be^[8]

1, 1, 4, 35, 481, 9042, 216077, 6271057, 214248958, 8424002973, 374708368981, 18604033129948, 1019915376831963, ... (sequence A287886 in the OEIS )

Related Research Articles

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In the mathematical area of graph theory, a clique 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 $is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.$

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes nor odd antiholes. It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002 and published by them in 2006.

In the mathematical field of graph theory, the complement or inverse of a graph $G$ is a graph $H$ on the same vertices such that two distinct vertices of $H$ are adjacent if and only if they are not adjacent in $G$ . That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there.

In graph theory, a cograph, or complement-reducible graph, or P₄-free graph, is a graph that can be generated from the single-vertex graph K₁ by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K₁ and is closed under complementation and disjoint union.

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 connecting pairs of vertices in that subset.

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 $A$ , $B$ , $C$ , and $D$ , the following inequality holds:

<span class="mw-page-title-main">Intersection graph</span> Graph representing intersections between given sets

In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them.

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest paths between each pair of a, b, and c.

In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.

In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from a breadth-first search, but it produces an ordering that is consistent with breadth-first search.

In the mathematical area of graph theory, an undirected graph $G$ is strongly chordal if it is a chordal graph and every cycle of even length in $G$ has an odd chord, i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle.

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.

In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals. Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.

In graph theory, a cop-win graph is an undirected graph on which the pursuer (cop) can always win a pursuit–evasion game against a robber, with the players taking alternating turns in which they can choose to move along an edge of a graph or stay put, until the cop lands on the robber's vertex. Finite cop-win graphs are also called dismantlable graphs or constructible graphs, because they can be dismantled by repeatedly removing a dominated vertex or constructed by repeatedly adding such a vertex. The cop-win graphs can be recognized in polynomial time by a greedy algorithm that constructs a dismantling order. They include the chordal graphs, and the graphs that contain a universal vertex.

References

1 2 Kay, David C.; Chartrand, Gary (1965), "A characterization of certain ptolemaic graphs", Canadian Journal of Mathematics , 17: 342–346, doi: 10.4153/CJM-1965-034-0 , MR 0175113 .
1 2 3 Howorka, Edward (1981), "A characterization of Ptolemaic graphs", Journal of Graph Theory , 5 (3): 323–331, doi:10.1002/jgt.3190050314, MR 0625074 .
1 2 "Graphclass: ptolemaic", Information System on Graph Classes and their Inclusions, retrieved 2016-06-05.
↑ McKee, Terry A. (2010), "Clique graph representations of Ptolemaic graphs", Discussiones Mathematicae Graph Theory, 30 (4): 651–661, doi:10.7151/dmgt.1520, MR 2761626 .
↑ Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986), "Distance-hereditary graphs", Journal of Combinatorial Theory , Series B, 41 (2): 182–208, doi:10.1016/0095-8956(86)90043-2, MR 0859310 .
1 2 Uehara, Ryuhei; Uno, Yushi (2009), "Laminar structure of Ptolemaic graphs with applications", Discrete Applied Mathematics , 157 (7): 1533–1543, doi:10.1016/j.dam.2008.09.006, MR 2510233 .
↑ Farber, Martin; Jamison, Robert E. (1986), "Convexity in graphs and hypergraphs", SIAM Journal on Algebraic and Discrete Methods , 7 (3): 433–444, doi:10.1137/0607049, hdl: 10338.dmlcz/127659 , MR 0844046 .
↑ Bahrani, Maryam; Lumbroso, Jérémie (2018), "Enumerations, forbidden subgraph characterizations, and the split-decomposition", Electronic Journal of Combinatorics, 25 (4)

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[kc-1] 1 2 Kay, David C.; Chartrand, Gary (1965), "A characterization of certain ptolemaic graphs", Canadian Journal of Mathematics , 17: 342–346, doi: 10.4153/CJM-1965-034-0 , MR 0175113 .

[how-2] 1 2 3 Howorka, Edward (1981), "A characterization of Ptolemaic graphs", Journal of Graph Theory , 5 (3): 323–331, doi:10.1002/jgt.3190050314, MR 0625074 .

[isgci-3] 1 2 "Graphclass: ptolemaic", Information System on Graph Classes and their Inclusions, retrieved 2016-06-05.

[4] McKee, Terry A. (2010), "Clique graph representations of Ptolemaic graphs", Discussiones Mathematicae Graph Theory, 30 (4): 651–661, doi:10.7151/dmgt.1520, MR 2761626 .

[5] Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986), "Distance-hereditary graphs", Journal of Combinatorial Theory , Series B, 41 (2): 182–208, doi:10.1016/0095-8956(86)90043-2, MR 0859310 .

[uu-6] 1 2 Uehara, Ryuhei; Uno, Yushi (2009), "Laminar structure of Ptolemaic graphs with applications", Discrete Applied Mathematics , 157 (7): 1533–1543, doi:10.1016/j.dam.2008.09.006, MR 2510233 .

[7] Farber, Martin; Jamison, Robert E. (1986), "Convexity in graphs and hypergraphs", SIAM Journal on Algebraic and Discrete Methods , 7 (3): 433–444, doi:10.1137/0607049, hdl: 10338.dmlcz/127659 , MR 0844046 .

[8] Bahrani, Maryam; Lumbroso, Jérémie (2018), "Enumerations, forbidden subgraph characterizations, and the split-decomposition", Electronic Journal of Combinatorics, 25 (4)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]