Gráfico ptolemaico

El gráfico de gemas o de 3 abanicos no es ptolemaico.

En teoría de grafos , un grafo ptolemaico es un grafo no dirigido cuyas distancias de ruta más cortas obedecen a la desigualdad de Ptolomeo , que a su vez recibió su nombre del astrónomo y matemático griego Ptolomeo . Los grafos ptolemaicos son exactamente los grafos que son tanto cordales como hereditarios de la distancia ; incluyen los grafos de bloques ^[1] y son una subclase de los grafos perfectos .

Caracterización

Un grafo es ptolemaico si y sólo si obedece cualquiera de las siguientes condiciones equivalentes:

Las distancias de camino más cortas obedecen a la desigualdad de Ptolomeo : para cada cuatro vértices $u$ , $v$ , $w$ y $x$ , se cumple la desigualdad $d (u, v) d (w, x) + d (u, x) d (v, w) \geq d (u, w) d (v, x)$ . ^[1] Por ejemplo, el grafo de gemas (3-abanico) en la ilustración no es ptolemaico, porque en este grafo $d (u, w) d (v, x) = 4$ , mayor que $d (u, v) d (w, x) + d (u, x) d (v, w) = 3$ .
Por cada dos camarillas máximas superpuestas , la intersección de las dos camarillas es un separador que divide las diferencias de las dos camarillas. ^[2] En la ilustración del gráfico de gemas, esto no es cierto: las camarillas $uvy$ y $wxy$ no están separadas por su intersección, $y$ , porque hay un borde $vw$ que conecta las camarillas pero evita la intersección.
Cada ciclo $de k$ vértices tiene al menos $3($ $k$ $- 3)/2$ diagonales. ^[2]
El grafo es a la vez cordal (cada ciclo de longitud mayor que tres tiene una diagonal) y hereditario de la distancia (cada subgrafo inducido conexo tiene las mismas distancias que el grafo completo). ^[2] La gema mostrada es cordal pero no hereditaria de la distancia: en el subgrafo inducido por $uvwx$ , la distancia de $u$ a $x$ es 3, mayor que la distancia entre los mismos vértices en el grafo completo. Debido a que tanto los grafos cordales como los hereditarios de la distancia son grafos perfectos , también lo son los grafos ptolemaicos. ^[3]
El gráfico es cordal y no contiene una gema inducida, un gráfico formado al agregar dos diagonales que no se cruzan a un pentágono. ^[3]
El gráfico es hereditario en función de la distancia y no contiene un ciclo inducido de 4 ciclos . ^[4]
El grafo puede construirse a partir de un único vértice mediante una secuencia de operaciones que añaden un nuevo vértice de grado uno (colgante), o duplican (gemelo) un vértice existente, con la excepción de que una operación de gemelo en la que el nuevo vértice duplicado no es adyacente a su gemelo (gemelos falsos) solo puede aplicarse cuando los vecinos de los gemelos forman una camarilla. Estas tres operaciones sin excepción forman todos los grafos hereditarios de distancia. Para formar todos los grafos ptolemaicos, no es suficiente utilizar vértices colgantes y gemelos verdaderos; a veces también se requiere el caso excepcional de los gemelos falsos. ^[5]
El diagrama de Hasse de la relación de subconjuntos en intersecciones no vacías de camarillas máximas forma un árbol orientado . ^[6]
Los subconjuntos convexos de vértices (subconjuntos que contienen cada camino más corto entre dos vértices en el subconjunto) forman una geometría convexa . Es decir, cada conjunto convexo puede alcanzarse desde el conjunto de vértices completo eliminando repetidamente un vértice extremo, uno que no pertenece a ningún camino más corto entre los vértices restantes. ^[7] En la gema, el conjunto convexo $uxy$ no puede alcanzarse de esta manera, porque ni $v$ ni $w$ son extremos.

Complejidad computacional

A partir de la caracterización mediante árboles orientados, los grafos ptolemaicos pueden reconocerse en tiempo lineal . ^[6]

Enumeración

La función generadora de grafos ptolemaicos se puede describir simbólicamente , lo que permite el cálculo rápido de la cantidad de estos grafos. Con base en este método, se ha encontrado que la cantidad de grafos ptolemaicos con $n$ vértices etiquetados, para , es ^[8] $n=1,2,3,\puntos$

1, 1, 4, 35, 481, 9042, 216077, 6271057, 214248958, 8424002973, 374708368981, 18604033129948, 1019915376831963, ... (secuencia A287886 en la OEIS )

Referencias

^ ab Kay, David C.; Chartrand, Gary (1965), "Una caracterización de ciertos grafos ptolemaicos", Revista Canadiense de Matemáticas , 17 : 342–346, doi : 10.4153/CJM-1965-034-0 , MR 0175113.
^ abc Howorka, Edward (1981), "Una caracterización de los grafos ptolemaicos", Journal of Graph Theory , 5 (3): 323–331, doi :10.1002/jgt.3190050314, MR 0625074.
^ ab "Graphclass: ptolemaic", Sistema de información sobre clases de grafos y sus inclusiones , consultado el 5 de junio de 2016.
^ McKee, Terry A. (2010), "Representaciones gráficas de camarilla de grafos ptolemaicos", Discussiones Mathematicae Graph Theory , 30 (4): 651–661, doi :10.7151/dmgt.1520, MR 2761626.
^ Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986), "Gráficos hereditarios de distancia", Journal of Combinatorial Theory , Serie B, 41 (2): 182–208, doi :10.1016/0095-8956(86)90043-2, MR 0859310.
^ ab Uehara, Ryuhei; Uno, Yushi (2009), "Estructura laminar de grafos ptolemaicos con aplicaciones", Discrete Applied Mathematics , 157 (7): 1533–1543, doi :10.1016/j.dam.2008.09.006, MR 2510233.
^ Farber, Martin; Jamison, Robert E. (1986), "Convexidad en grafos e hipergrafos", 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), "Enumeraciones, caracterizaciones de subgrafos prohibidos y descomposición dividida", Electronic Journal of Combinatorics , 25 (4)