Graphe ptolémaïque

Un graphe ptolémaïque.

Le graphe gemme ou 3-fan n'est pas ptolémaïque.

Un graphe en blocgraphe en bloc est un cas particulier d'un graphe ptolémaïque

Trois opérations qui permettent de construire tout graphe distance-héréditaire. Pour les graphes ptolémaïques, les voisins de « faux jumeaux » doivent former une clique, ce qui empêche la construction d'un cycle à 4 sommets, montré ici.

En théorie des graphes, un graphe de Ptolémée ou graphe ptolémaïque est un graphe non orienté dont les distances des plus courts chemins entre sommets les plus courtes obéissent à l'inégalité de Ptolémée, qui à son tour a été nommée d'après l'astronome et mathématicien grec Ptolémée . Les graphes de Ptolémée sont exactement les graphes qui sont à la fois cordaux et à distance héréditaire ; ils incluent les graphes par blocs et sont une sous-classe des graphes parfaits .

Caractérisations

Un graphe est ptolémaïque si et seulement s'il vérifie une des conditions équivalentes suivantes :

• Les distances des chemins les plus courts vérifient l'inégalité de Ptolémée : quatre sommets quelconques $u,v,w$, et $x$ vérifient l'inégalité

$d(u,v)d(w,x)+d(u,x)d(v,w)\geq d(u,w)d(v,x)$

Par exemple, le graphe gemme de l'illustration n'est pas ptolémaïque, car dans ce graphe

$d(u,w)d(v,x)=4>d(u,v)d(w,x)+d(u,x)d(v,w)=3$.

• L'intersection de deux cliques maximales chevauchantes est un séparateur qui sépare les différences des deux cliques. Dans le graphe gemme, ce n'est pas le cas : les cliques uvy et wxy ne sont pas séparées par leur intersection y, car l'arête vw relie les cliques et évite l'intersection.
• Tout cycle à k sommets a au moins 3(k − 3)/2 diagonales.
• Le graphe est à la fois cordal (chaque cycle de longueur supérieure à trois a une diagonale) et à distance héréditaire (chaque sous-graphe induit connexe a les mêmes distances que le graphe tout entier). Le graphe gemme ci-dessus est cordal mais n'es pas à distance héréditaire : dans le sous-graphe induit par uvwx, la distance de u à x est de 3, et est donc supérieure à la distance entre les mêmes sommets dans le graphe entier. Comme les graphes cordaux et à distance héréditaire sont des graphes parfaits, les graphes de Ptolémaïque le sont aussi.
• Le graphe est cordal et ne contient pas de graphe gemme induit.
• Le graphe est à distance héréditaire ne contient pas de cycle induit de longueur 4.
• Le graphe peut être construit à partir d'un sommet unique par une séquence d'opérations qui ajoutent un nouveau sommet pendant (de degré un) ou qui dupliquent un sommet existant sous réserve que le nouveau sommet dupliqué est adjacent à son jumeau (vrai jumeaux) sauf si les voisins des jumeaux forment une clique. Ces trois opérations, produisent tous les graphe à distance héréditaire. Pour obtenir tous les graphes ptolémaïques, il ne suffit pas d'utiliser des sommets pendants et de vrais jumeaux ; le cas exceptionnel des faux jumeaux est aussi nécessaire.
• Le diagramme de Hasse de la relation d'inclusion des intersections non vides de cliques maximales est un arbre orienté.
• Les sous-ensembles de sommets qui sont convexes (ce sont des ensembles qui contiennent chaque chemin le plus court entre deux sommets du sous-ensemble) forment une géométrie convexe. Cela signifie que tout ensemble convexe peut être obtenu à partir de l'ensemble de sommets tout entier en supprimant à plusieurs reprises un sommet « extrême », c'est-à-dire un sommet qui n'appartient à aucun des chemins les plus courts entre les sommets restants. Dans le graphe gemme, l'ensemble convexe uxy ne peut pas être obtenu de cette manière, car ni v ni w sont des sommets extrêmes.

Complexité de calcul

En vertu de la caractérisation par arbres orientés, les graphes de Ptolémée peuvent être reconnus en temps linéaire.

Énumération

La série génératrice des graphes ptolémaïques peut être décrite par des méthodes de combinatoire analytique ; ceci permet le calcul rapide du nombre de ces graphes. Le nombre de graphes ptolémaïques à n sommets étiquetés, pour $n=1,2,3,\dots$, est le suivant :

1, 1, 4, 35, 481, 9042, 216077, 6271057, 214248958, 8424002973, 374708368981, 18604033129948, 1019915376831963, ... suite A287886 de l'OEIS

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Ptolemaic graph » (voir la liste des auteurs).

Bibliographie

• Arun Anil, Manoj Changat, Tanja Gologranc et Baiju Sukumaran, « Ptolemaic and planar cover-incomparability graphs », Order,‎ 2021 (ISSN 0167-8094, DOI 10.1007/s11083-021-09549-4).
• Van Bang Le, Andrea Oversberg et Oliver Schaudt, « Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs », Theoretical Computer Science, vol. 602,‎ 2015, p. 39–49 (DOI 10.1016/j.tcs.2015.07.060).
• Andreas Brandstädt et Christian Hundt, « Ptolemaic Graphs and Interval Graphs Are Leaf Powers », Springer Lecture Notes in Computer Science, vol. 4957 « LATIN 2008: Theoretical Informatics »,‎ 2008, p. 479–491 (DOI 10.1007/978-3-540-78773-0_42).
• Lilian Markenzon et Christina Fraga Esteves Maciel Waga, « New results on ptolemaic graphs », Discrete Applied Mathematics, vol. 196,‎ 2015, p. 135–140 (DOI 10.1016/j.dam.2014.03.024).
• Ryuhei Uehara et Yushi Uno, « Laminar structure of ptolemaic graphs with applications », Discrete Applied Mathematics, vol. 157, n^o 7,‎ 2009, p. 1533–1543 (DOI 10.1016/j.dam.2008.09.006).