Un gráfico autocomplementario es un gráfico que es isomorfo a su complemento . Los gráficos autocomplementarios no triviales más simples son el gráfico de trayectoria de 4 vértices y el gráfico de ciclo de 5 vértices . No existe una caracterización conocida de los gráficos autocomplementarios.
Ejemplos de
Cada gráfico de Paley es autocomplementario. [1] Por ejemplo, el gráfico de la torre de 3 × 3 (el gráfico 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 gráficos autocomplementarios fuertemente regulares con menos de 37 vértices son gráficos de Paley; sin embargo, hay gráficas fuertemente regulares en 37, 41 y 49 vértices que no son gráficas de Paley. [3]
El gráfico de Rado es un gráfico autocomplementario infinito. [4]
Propiedades
Un gráfico autocomplementario de n -vértices tiene exactamente la mitad del número de aristas del gráfico 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 entre 4, n debe ser congruente con 0 o 1 mod 4; por ejemplo, un gráfico de 6 vértices no puede ser autocomplementario.
Complejidad computacional
Los problemas de comprobar si dos gráficos autocomplementarios son isomorfos y de comprobar si un gráfico dado es autocomplementario son equivalentes en tiempo polinómico al problema general de isomorfismo de grafos . [5]
Referencias
- ^ a b Sachs, Horst (1962), "Über selbstkomplementäre Graphen", Publicationes Mathematicae Debrecen , 9 : 270-288, MR 0151953.
- ^ Shpectorov, S. (1998), "Complementary l 1 -graphs", Discrete Mathematics , 192 (1–3): 323–331, doi : 10.1016 / S0012-365X (98) 0007X-1 , MR 1656740.
- ^ Rosenberg, IG (1982), "Gráficos autocomplementarios regulares y fuertemente regulares", Teoría y práctica de combinatoria , North-Holland Math. Stud., 60 , Amsterdam: North-Holland, págs. 223-238, MR 0806985.
- ^ Cameron, Peter J. (1997), "El gráfico aleatorio", Las matemáticas de Paul Erdős, II , Algorithms Combin., 14 , Berlín: Springer, págs. 333–351, arXiv : 1301.7544 , Bibcode : 2013arXiv1301.7544C , MR 1425227. Ver en particular la Proposición 5.
- ^ Colbourn, Marlene J .; Colbourn, Charles J. (1978), "Grafos isomorfistas y autocomplementarios", SIGACT News , 10 (1): 25-29, doi : 10.1145 / 1008605.1008608.
enlaces externos
- Weisstein, Eric W. "Gráfico autocomplementario" . MathWorld .