Gráfico impar

En la teoría de grafos, los gráficos impares O n  son una familia de gráficos simétricos con una circunferencia impar alta definida en algunas familias de conjuntos . Incluyen y generalizan los gráficos de Petersen .

Definiciones y ejemplos

El gráfico impar O n tiene un vértice para cada uno de los ( n  − 1) subconjuntos de elementos del conjunto de (2 n  − 1) elementos. Dos vértices están conectados por una arista si y solo si los subconjuntos correspondientes no se cruzan [4] . Entonces, O n  es el gráfico de Kneser KG (2 n  − 1, n  − 1), O 2  es un triángulo y O 3  es el familiar gráfico de Petersen .

Los gráficos impares generalizados incluyen gráficos impares y gráficos cúbicos plegables, y se definen como gráficos de distancia regular con diámetro n  − 1 y circunferencia impar 2 n  − 1 para algún n [5] .

Historia y aplicaciones

Aunque los gráficos de Petersen se conocen desde 1898, su definición como "gráficos impares" se remonta a Kowalewski [6] , en el que estudia el gráfico O 4 impar [2] [6] . Los gráficos impares se estudian debido a su uso en la teoría de gráficos químicos para modelar el cambio de iones de carbono .[7] [8] . También se utilizan como topología de red en computación paralela [9] .

La notación O n para estos gráficos fue propuesta por Norman Biggsen 1972 [10] . Biggs y Tony Gardinerexplicar el nombre de los gráficos impares en una monografía inédita de 1974: cada borde de un gráfico impar se puede asociar con un solo elemento X , que es "hombre extraño fuera" (que se puede traducir como "un jugador sin compañero abandona el juego" ), es decir, el elemento no pertenece a ningún otro subconjunto asociado a vértices incidentes a la arista dada [11] [12] .

Propiedades

Un gráfico impar O n es un gráfico regular de grado n . Tiene vértices y aristas. Entonces el número de vértices para n = 1, 2,… será

1, 3, 10, 35, 126, 462, 1716, 6435 (secuencia A001700 en OEIS ).

Distancia y simetría

Si dos vértices en O n corresponden a conjuntos del mismo tamaño, que difieren en k elementos, entonces puede obtener el segundo del primero en 2k pasos, eliminando o agregando un elemento en cada paso. Si 2 k  <  n , entonces este es el camino más corto . De lo contrario, puede encontrar un camino más corto de este tipo si comienza con un conjunto complementario al segundo conjunto y luego obtiene el segundo conjunto dando un paso más. Así, el diámetro del gráfico O n es igual a n  − 1 [1] [2] .

Cualquier gráfico impar es transitivo de 3 arcos  : cualquier ruta orientada de tres aristas en un gráfico impar se puede asignar a cualquier ruta de este tipo utilizando la simetría de gráfico [13] . Los gráficos impares son transitivos en distancia porque son regulares en distancia [2] . Como gráficos de distancia regular, se definen únicamente por su matriz de intersección; ningún otro gráfico de distancia regular puede tener los mismos parámetros que un gráfico impar [14] . Sin embargo, a pesar del alto grado de simetría, los gráficos O impares para n  > 2 nunca son gráficos de Cayley [15] .

Los gráficos impares con n ≥ 3 tienen una circunferencia de seis. Sin embargo, aunque no son gráficos bipartitos , sus ciclos impares son mucho más largos, es decir, el gráfico impar O n tiene una circunferencia impar 2 n  − 1. Si un gráfico n -regular tiene un diámetro n  − 1, la circunferencia impar es 2 n  − 1 y solo n valores propios diferentes , debe ser regular en distancia. Los gráficos regulares de distancia de diámetro n  - 1 y circunferencia impar 2n  - 1 se conocen como gráficos impares generalizados e incluyen gráficos cúbicos plegablesal igual que los propios gráficos impares [5] .

Conjuntos independientes y coloración de vértices

Sea O n  un gráfico impar definido en (2 n  − 1) subconjuntos de elementos de X , y sean x  elementos de X . Entonces, entre O n vértices, exactamente los vértices corresponden a conjuntos que contienen x . Dado que todos estos conjuntos contienen x , no son disjuntos y forman un conjunto independiente del gráfico O n . Así, O n tiene 2 n  − 1 conjuntos independientes distintos de tamaño . Del teorema de Erdős-Ko-Radose sigue que estos son los conjuntos independientes máximos del grafo O n . Por lo tanto, el número de independencia del gráfico O n es Además, cualquier conjunto independiente máximo debe tener esta forma, por lo que O n tiene exactamente 2 n  − 1 conjuntos independientes máximos [2] .

Si I  es el máximo conjunto independiente formado por el conjunto que contiene el elemento x , entonces el complemento del conjunto I  es el conjunto de vértices que no contienen x . Este complemento genera un emparejamiento en G. Cada vértice del conjunto independiente es adyacente a n vértices de la coincidencia, y cada vértice de la coincidencia es adyacente a n  − 1 vértices del conjunto independiente [2] . En vista de esta descomposición, y en vista de que los gráficos impares no son bipartitos, tienen un número cromático igual a tres - se puede asignar un color a los vértices del conjunto máximo independiente, y otros dos colores se pueden obtener de el emparejamiento generado por el complemento.

Coloración de bordes

Por el teorema de Vizing , el número de colores necesarios para colorear los bordes de un gráfico impar O n es n o n  + 1, y en el caso de los gráficos de Petersen O 3 es n  + 1. Si n  es una potencia de dos, el número de vértices en el gráfico es impar, de donde nuevamente se sigue que el número de colores en una coloración de borde es n  + 1 [16] . Sin embargo, O 5 , O 6 y O 7 se pueden colorear con n colores [2] [16] .

Biggs [10] explica este problema con la siguiente historia: Once jugadores de fútbol de la ciudad ficticia de Kroam quieren formar parejas de equipos de fútbol sala (queda una persona para arbitrar el partido) de 1386 formas diferentes y quieren programar partidos entre todas las parejas. , con seis partidos para cada equipo, deberán jugarse en días distintos de la semana, a falta de partidos los domingos. ¿Es posible? En esta historia, cada juego representa un borde O 6 , todos los días están representados por colores, y un borde de 6 colores para colorear el gráfico O 6 da el horario.

Gráficos impares y gráficos hamiltonianos

Los gráficos O 3 de Petersen  son gráficos no hamiltonianos bien conocidos, pero se ha demostrado que los gráficos O 4 a O 14 contienen ciclos hamiltonianos [8] [17] [18] [19] . Más rigurosamente, al combinar los problemas de encontrar ciclos hamiltonianos y el coloreado de bordes, uno puede dividir los bordes del gráfico O n (para n = 4, 5, 6, 7) en el entero inferior más cercano de ( n /2) ciclos hamiltonianos . Si n es impar, las aristas restantes forman una combinación perfecta [2] [16] . Para n  = 8, un número impar de vértices en O n no permite colorear las aristas con 8 colores, pero no cierra la posibilidad de descomponer en cuatro ciclos hamiltonianos.

La conjetura del ciclo hamiltoniano de Lovas asume que todo gráfico impar tiene un camino hamiltoniano y que todo gráfico O n impar con n  ≥ 4 tiene un ciclo hamiltoniano.

Notas

  1. ↑ 1 2 Norman L. Biggs. Grafos automórficos y la condición de Kerin // Geometriae Dedicata. - 1976. - Edición. 5 . - S. 117-127 . -doi : 10.1007/ BF00148146 .
  2. ↑ 1 2 3 4 5 6 7 8 Biggs, 1979
  3. ↑ Douglas B. Oeste. Introducción a la Teoría de Grafos. — 2do. - Englewood Cliffs, NJ: Prentice-Hall, 2000. - Pág. 17.
  4. ↑ Weisstein, Eric W. Odd Graph  en el sitio web de Wolfram MathWorld .
  5. ↑ 1 2 Edwin Van Dam, Willem H. Haemers. Una caracterización impar de los gráficos impares generalizados. — 2010.
  6. ↑ 1 2 A. Kowalewski. Dodekaederaufgabe als Buntordnungproblem // Sitzungsber de WR Hamilton. Akád. sabio Viena (Abt. IIa). - 1917. - T. 126 . - S. 67-90, 963-1007 . Como se cita en Biggs ( Biggs 1979 ).
  7. ↑ Alexandru T. Balaban, D. Fǎrcaşiu, R. Bǎnicǎ. Gráficos de desplazamientos múltiples 1, 2 en iones de carbonio y sistemas relacionados // Rev. habitación. Chim.. - 1966. - T. 11 . - S. 1205 .
  8. ↑ 1 2 Alexandru T. Balaban. Gráficos químicos, Parte XIII: Patrones combinatorios // Rev. Matemáticas rumana. Pures Appl.. - 1972. - Vol . 17 . - Pág. 3-16 .
  9. ↑ Arif Ghafoor, Theodore R. Bashkow. Un estudio de gráficos impares como redes de interconexión tolerantes a fallas // IEEE Transactions on Computing. - 1991. - T. 40 , núm. 2 . - S. 225-232 . -doi : 10.1109/ 12.73594 .
  10. ↑ 1 2 Norman Biggs. Problemas de investigación  // American Mathematical Monthly. - 1972. - T. 79 , núm. 9 _ - S. 1018-1020 . — .
  11. ↑ Andries Brouwer, Arjeh M. Cohen, A. Neumaier. Gráficos de distancia regular. - 1989. - ISBN 0-387-50619-5 .
  12. ↑ Ed Pegg Jr. Gráficos simétricos cúbicos. - Asociación Matemática de América , 2003. Archivado desde el original el 21 de agosto de 2010.
  13. ↑ Laszlo Babai. Manual de Combinatoria / Ronald L. Graham, Martin Grötschel, László Lovász. - Holanda Septentrional, 1995. - T. I. - S. 1447-1540.
  14. ↑ Luna Aeryung. Caracterización de las gráficas impares O k por parámetros // Matemática Discreta. - 1982. - T. 42 , núm. 1 . - S. 91-97 . - doi : 10.1016/0012-365X(82)90057-7 .
  15. ↑ CD Godsil. Más teoría de grafos impares // Matemáticas discretas. - 1980. - T. 32 , núm. 2 . - S. 205-207 . - doi : 10.1016/0012-365X(80)90055-2 .
  16. ↑ 1 2 3 Guy HJ Meredith, E. Keith Lloyd. Los futbolistas de Croam // Journal of Combinatorial Theory, Serie B. - 1973. - T. 15 . - S. 161-166 . - doi : 10.1016/0095-8956(73)90016-6 .
  17. ↑ Guy HJ Meredith, E. Keith Lloyd. Combinatoria (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972). Southend: Inst. Matemáticas. Appl, 1972. - S. 229-236 .
  18. ↑ Madre de Miguel. Los futbolistas de Rugby de Croam // Journal of Combinatorial Theory, Serie B. - 1976. - V. 20 . - S. 62-63 . - doi : 10.1016/0095-8956(76)90066-6 .
  19. ↑ Ian Shields, Carla D. Savage. Una nota sobre los ciclos de Hamilton en los gráficos de Kneser // Boletín del Instituto de Combinatoria y sus Aplicaciones. - 2004. - T. 40 . - S. 13-22 .

Literatura