Un gráfico ptolemaicoLa gráfica de gemas o 3 abanicos no es ptolemaica.Un gráfico de bloques , un caso especial de un gráfico ptolemaicoTres operaciones mediante las cuales se puede construir cualquier gráfico hereditario a distancia. Para los gráficos ptolemaicos, los vecinos de los falsos gemelos están restringidos a formar una camarilla, lo que impide la construcción del 4 ciclo que se muestra aquí.
Un grafo es ptolemaico si y sólo si obedece alguna de las siguientes condiciones equivalentes:
Las distancias de camino más cortas obedecen a la desigualdad de Ptolomeo : por cada cuatro vértices u , v , w y x , la desigualdad d ( u , v ) d ( w , x ) + d ( u , x ) d ( v , w ) ≥ d ( u , w ) d ( v , x ) se cumple. [1] Por ejemplo, la gráfica de gemas (3 abanicos) en la ilustración no es ptolemaica, porque en esta gráfica d ( u , w ) d ( v , x ) = 4 , mayor que d ( u , v ) d ( w , x ) + re ( 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 una arista vw que conecta las camarillas pero evita la intersección.
Cada k -ciclo de vértices tiene al menos 3( k − 3)/2 diagonales. [2]
El gráfico es cordal (cada ciclo de longitud mayor que tres tiene una diagonal) y hereditario a distancia (cada subgrafo inducido conectado tiene las mismas distancias que el gráfico completo). [2] La gema que se muestra es cordal pero no hereditaria por 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 todo el gráfico. Debido a que tanto las gráficas cordales como las hereditarias de distancia son gráficas perfectas , también lo son las gráficas ptolemaicas. [3]
La gráfica es cordal y no contiene una gema inducida, una gráfica formada sumando dos diagonales que no se cruzan a un pentágono. [3]
El gráfico es hereditario por distancia y no contiene un 4 ciclo inducido . [4]
El gráfico se puede construir a partir de un solo vértice mediante una secuencia de operaciones que agregan un nuevo vértice de grado uno (colgante) o duplican (gemelo) un vértice existente, con la excepción de una operación gemela en la que el nuevo vértice duplicado no está adyacente a su gemelo (falsos gemelos) sólo se puede aplicar cuando los vecinos de los gemelos forman una camarilla. Estas tres operaciones, sin excepción, forman todo el gráfico hereditario a distancia. Para formar todos los grafos ptolemaicos, no basta con utilizar vértices colgantes y gemelos verdaderos; A veces también se requiere el caso excepcional de falsos gemelos. [5]
El diagrama de Hasse de la relación de subconjunto 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 del subconjunto) forman una geometría convexa . Es decir, se puede llegar a cada conjunto convexo desde todo el conjunto de vértices 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 se puede alcanzar de esta manera, porque ni v ni w son extremos.
Complejidad computacional
Basándose en la caracterización mediante árboles orientados, los gráficos ptolemaicos pueden reconocerse en tiempo lineal . [6]
Enumeración
La función generadora de gráficos ptolemaicos se puede describir simbólicamente , lo que permite el cálculo rápido de los números de estos gráficos. Con base en este método, se ha encontrado que el número de gráficos ptolemaicos con n vértices etiquetados, para , es [8]
^ ab Kay, David C.; Chartrand, Gary (1965), "Una caracterización de ciertos gráficos ptolemaicos", Canadian Journal of Mathematics , 17 : 342–346, doi : 10.4153/CJM-1965-034-0 , MR 0175113.
^ abc Howorka, Edward (1981), "Una caracterización de los gráficos 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 gráficos y sus inclusiones , consultado el 5 de junio de 2016.
^ McKee, Terry A. (2010), "Representaciones de gráficos camarillas de gráficos 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, SEÑOR 0859310.
^ ab Uehara, Ryuhei; Uno, Yushi (2009), "Estructura laminar de gráficos ptolemaicos con aplicaciones", Matemáticas aplicadas discretas , 157 (7): 1533–1543, doi :10.1016/j.dam.2008.09.006, MR 2510233.
