stringtranslate.com

Gráfico autocomplementario

  Gráfico A
  Complemento gráfico de A
El gráfico A es isomorfo a su complemento.

En el campo matemático de la teoría de grafos , un grafo autocomplementario es un grafo que es isomorfo a su complemento . Los grafos autocomplementarios no triviales más simples son el grafo de trayectoria de 4 vértices y el grafo de ciclo de 5 vértices . No se conoce ninguna caracterización de los grafos autocomplementarios.

Ejemplos

Todo grafo de Paley es autocomplementario. [1] Por ejemplo, el grafo de la torre de 3 × 3 (el grafo de Paley de orden nueve) es autocomplementario, por una simetría que mantiene el vértice central en su lugar pero intercambia los roles de los cuatro puntos medios laterales y las cuatro esquinas de la cuadrícula. [2] Todos los grafos autocomplementarios fuertemente regulares con menos de 37 vértices son grafos de Paley; sin embargo, hay grafos fuertemente regulares en 37, 41 y 49 vértices que no son grafos de Paley. [3]

El gráfico de Rado es un gráfico autocomplementario infinito. [4]

Propiedades

Un grafo autocomplementario de n vértices tiene exactamente la mitad de aristas que el grafo completo , es decir, n ( n − 1)/4 aristas, y (si hay más de un vértice) debe tener un diámetro de 2 o 3. [1] Dado que n ( n − 1) debe ser divisible por 4, n debe ser congruente con 0 o 1 módulo 4; por ejemplo, un grafo de 6 vértices no puede ser autocomplementario.

Complejidad computacional

Los problemas de comprobar si dos grafos autocomplementarios son isomorfos y de comprobar si un grafo dado es autocomplementario son equivalentes en tiempo polinomial al problema general de isomorfismo de grafos . [5]

Referencias

  1. ^ ab Sachs, Horst (1962), "Über selbstkomplementäre Graphen", Publicationes Mathematicae Debrecen , 9 : 270–288, SEÑOR  0151953.
  2. ^ Shpectorov, S. (1998), " Gráficos l 1 complementarios", Matemáticas discretas , 192 (1–3): 323–331, doi :10.1016/S0012-365X(98)0007X-1, MR  1656740.
  3. ^ Rosenberg, IG (1982), "Gráficos autocomplementarios regulares y fuertemente regulares", Teoría y práctica de la combinatoria , North-Holland Math. Stud., vol. 60, Ámsterdam: North-Holland, págs. 223-238, MR  0806985.
  4. ^ Cameron, Peter J. (1997), "El gráfico aleatorio", Las matemáticas de Paul Erdős, II , Algorithms Combin., vol. 14, Berlín: Springer, págs. 333–351, arXiv : 1301.7544 , Bibcode :2013arXiv1301.7544C, MR  1425227. Véase en particular la Proposición 5.
  5. ^ Colbourn, Marlene J.; Colbourn, Charles J. (1978), "Isomorfismo de grafos y grafos autocomplementarios", SIGACT News , 10 (1): 25–29, doi :10.1145/1008605.1008608.

Enlaces externos