Ptolemaic graph

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 {{mvar|u}}, {{mvar|v}}, {{mvar|w}}, and {{mvar|x}}, the inequality {{math|d(u,v)d(w,x) + d(u,x)d(v,w) ≥ d(u,w)d(v,x)}} holds.{{citation

| last1 = Kay | first1 = David C.

| last2 = Chartrand | first2 = Gary | author2-link = Gary Chartrand

| doi = 10.4153/CJM-1965-034-0

| journal = Canadian Journal of Mathematics

| mr = 0175113

| pages = 342–346

| title = A characterization of certain ptolemaic graphs

| volume = 17

| year = 1965 | doi-access = free

}}. For instance, the gem graph (3-fan) in the illustration is not Ptolemaic, because in this graph {{math|1=d(u,w)d(v,x) = 4}}, greater than {{math|1=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.{{citation

| last = Howorka | first = Edward

| doi = 10.1002/jgt.3190050314

| issue = 3

| journal = Journal of Graph Theory

| mr = 625074

| pages = 323–331

| title = A characterization of Ptolemaic graphs

| volume = 5

| year = 1981}}. In the illustration of the gem graph, this is not true: cliques {{mvar|uvy}} and {{mvar|wxy}} are not separated by their intersection, {{mvar|y}}, because there is an edge {{mvar|vw}} that connects the cliques but avoids the intersection.

• Every {{mvar|k}}-vertex cycle has at least {{math|3(k − 3)/2}} diagonals.
• 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). The gem shown is chordal but not distance-hereditary: in the subgraph induced by {{mvar|uvwx}}, the distance from {{mvar|u}} to {{mvar|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.
• The graph is chordal and does not contain an induced gem, a graph formed by adding two non-crossing diagonals to a pentagon.{{citation|url=http://www.graphclasses.org/classes/gc_95.html|title=Graphclass: ptolemaic|work=Information System on Graph Classes and their Inclusions|accessdate=2016-06-05}}.
• The graph is distance-hereditary and does not contain an induced 4-cycle.{{citation

| last = McKee | first = Terry A.

| doi = 10.7151/dmgt.1520

| issue = 4

| journal = Discussiones Mathematicae Graph Theory

| mr = 2761626

| pages = 651–661

| title = Clique graph representations of Ptolemaic graphs

| volume = 30

| year = 2010}}.

• 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.{{citation

| last1 = Bandelt | first1 = Hans-Jürgen

| last2 = Mulder | first2 = Henry Martyn

| doi = 10.1016/0095-8956(86)90043-2

| issue = 2

| journal = Journal of Combinatorial Theory

| mr = 859310

| pages = 182–208

| series = Series B

| title = Distance-hereditary graphs

| volume = 41

| year = 1986| doi-access =

}}.

• The Hasse diagram of the subset relation on nonempty intersections of maximal cliques forms an oriented tree.{{citation

| last1 = Uehara | first1 = Ryuhei

| last2 = Uno | first2 = Yushi

| doi = 10.1016/j.dam.2008.09.006

| issue = 7

| journal = Discrete Applied Mathematics

| mr = 2510233

| pages = 1533–1543

| title = Laminar structure of Ptolemaic graphs with applications

| volume = 157

| year = 2009| doi-access =

}}.

• 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.{{citation

| last1 = Farber | first1 = Martin

| last2 = Jamison | first2 = Robert E.

| doi = 10.1137/0607049

| issue = 3

| journal = SIAM Journal on Algebraic and Discrete Methods

| mr = 844046

| pages = 433–444

| title = Convexity in graphs and hypergraphs

| volume = 7

| year = 1986| hdl = 10338.dmlcz/127659

| hdl-access = free

}}. In the gem, the convex set {{mvar|uxy}} cannot be reached in this way, because neither {{mvar|v}} nor {{mvar|w}} is extreme.

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

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 {{mvar|n}} labeled vertices, for $n=1,2,3,\backslash dots$, has been found to be{{citation

| last1 = Bahrani | first1 = Maryam

| last2 = Lumbroso | first2 = Jérémie

| issue = 4

| journal = Electronic Journal of Combinatorics

| title = Enumerations, forbidden subgraph characterizations, and the split-decomposition

| url = http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p47

| volume = 25

| year = 2018| doi = 10.37236/6431

| doi-access = free

}}

:1, 1, 4, 35, 481, 9042, 216077, 6271057, 214248958, 8424002973, 374708368981, 18604033129948, 1019915376831963, ... {{OEIS|A287886}}

{{reflist}}

Category:Graph families

Category:Perfect graphs

Category:Intersection classes of graphs

Category:Ptolemy

Category:Eponyms in mathematics