Gráfico impar

Familia de grafos simétricos que generalizan el grafo de Petersen

El gráfico impar ${\displaystyle O_{4}=KG(7,3)}$

En el campo matemático de la teoría de grafos , los grafos impares son una familia de grafos simétricos definidos a partir de ciertos sistemas de conjuntos . Entre ellos se encuentra y generaliza el grafo de Petersen .

Los grafos impares tienen una circunferencia impar alta , lo que significa que contienen ciclos impares largos pero ninguno corto. Sin embargo , su nombre no proviene de esta propiedad, sino del hecho de que cada arista del grafo tiene un "odd man out", un elemento que no participa en los dos conjuntos conectados por la arista.

Definición y ejemplos

El grafo impar tiene un vértice para cada uno de los subconjuntos de elementos de un conjunto de elementos. Dos vértices están conectados por una arista si y solo si los subconjuntos correspondientes son disjuntos . ^[2] Es decir, es el grafo de Kneser . ${\displaystyle O_{n}}$ ${\displaystyle (n-1)}$ ${\displaystyle (2n-1)}$ ${\displaystyle O_{n}}$ ${\displaystyle KG(2n-1,n-1)}$

${\displaystyle O_{2}}$es un triángulo, mientras que es el conocido gráfico de Petersen . ${\displaystyle O_{3}}$

Los grafos impares generalizados se definen como grafos regulares en cuanto a distancia con diámetro y circunferencia impares para algún . ^[4] Incluyen los grafos impares y los grafos cúbicos plegados . ${\displaystyle n-1}$ ${\displaystyle 2n-1}$ ${\displaystyle n}$

Historia y aplicaciones

Aunque el grafo de Petersen se conoce desde 1898, su definición como grafo impar se remonta al trabajo de Kowalewski (1917), quien también estudió el grafo impar . ^{[2] [5]} Los grafos impares se han estudiado por sus aplicaciones en la teoría de grafos químicos , en el modelado de los desplazamientos de iones de carbonio . ^{[6] [7]} También se han propuesto como una topología de red en computación paralela . ^[8] ${\displaystyle O_{4}}$

La notación para estos gráficos fue introducida por Norman Biggs en 1972. ^[9] Biggs y Tony Gardiner explican el nombre de los gráficos impares en un manuscrito inédito de 1974: a cada borde de un gráfico impar se le puede asignar el elemento único que es el "extra", es decir, no es miembro de ninguno de los subconjuntos asociados con los vértices incidentes a ese borde. ^{[10] [11]} ${\displaystyle O_{n}}$

Propiedades

El grafo impar es regular de grado . Tiene vértices y aristas. Por lo tanto, el número de vértices para es ${\displaystyle O_{n}}$ ${\displaystyle n}$ ${\displaystyle {\tbinom {2n-1}{n-1}}}$ ${\displaystyle n{\tbinom {2n-1}{n-1}}/2}$ ${\displaystyle n=1,2,\dots }$

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

Distancia y simetría

Si dos vértices en corresponden a conjuntos que difieren entre sí por la eliminación de elementos de un conjunto y la adición de elementos diferentes, entonces se puede llegar a ellos uno desde el otro en pasos, cada par de los cuales realiza una única adición y eliminación. Si , este es un camino más corto ; en caso contrario, es más corto encontrar un camino de este tipo desde el primer conjunto hasta un conjunto complementario al segundo, y luego llegar al segundo conjunto en un paso más. Por lo tanto, el diámetro de es . ^{[1] [2]} ${\displaystyle O_{n}}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 2k}$ ${\displaystyle 2k<n}$ ${\displaystyle O_{n}}$ ${\displaystyle n-1}$

Todo grafo impar es transitivo en tres arcos : cada camino dirigido de tres aristas en un grafo impar puede transformarse en cualquier otro camino de este tipo por una simetría del grafo. ^[12] Los grafos impares son transitivos en distancia , por lo tanto regulares en distancia . ^[2] Como grafos regulares en distancia, se definen de forma única por su matriz de intersecciones: ningún otro grafo regular en distancia puede tener los mismos parámetros que un grafo impar. ^[13] Sin embargo, a pesar de su alto grado de simetría, los grafos impares para nunca son grafos de Cayley . ^[14] ${\displaystyle O_{n}}$ ${\displaystyle n>2}$

Debido a que los gráficos impares son regulares y transitivos en sus aristas , su conectividad de vértices es igual a su grado, . ^[15] ${\displaystyle n}$

Los grafos impares tienen una circunferencia de seis; sin embargo, aunque no son grafos bipartitos , sus ciclos impares son mucho más largos. En concreto, el grafo impar tiene una circunferencia impar . Si un grafo -regular tiene un diámetro y una circunferencia impar , y solo tiene valores propios distintos , debe ser regular en distancias. Los grafos regulares en distancias con un diámetro y una circunferencia impar se conocen como grafos impares generalizados , e incluyen los grafos cúbicos plegados , así como los propios grafos impares. ^[4] ${\displaystyle n>3}$ ${\displaystyle O_{n}}$ ${\displaystyle 2n-1}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle 2n-1}$ ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle 2n-1}$

Conjuntos independientes y coloración de vértices

Sea un grafo impar definido a partir de los subconjuntos de un conjunto de elementos , y sea cualquier miembro de . Entonces, entre los vértices de , exactamente los vértices corresponden a conjuntos que contienen a . Como todos estos conjuntos contienen a , no son disjuntos y forman un conjunto independiente de . Es decir, tiene diferentes conjuntos independientes de tamaño . Del teorema de Erdős–Ko–Rado se deduce que estos son los conjuntos independientes máximos de , es decir, el número de independencia de es Además, todo conjunto independiente máximo debe tener esta forma, por lo que tiene exactamente conjuntos independientes máximos. ^[2] ${\displaystyle O_{n}}$ ${\displaystyle (2n-1)}$ ${\displaystyle X}$ ${\displaystyle x}$ ${\displaystyle X}$ ${\displaystyle O_{n}}$ ${\displaystyle {\tbinom {2n-2}{n-2}}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle O_{n}}$ ${\displaystyle O_{n}}$ ${\displaystyle 2n-1}$ ${\displaystyle {\tbinom {2n-2}{n-2}}}$ ${\displaystyle O_{n}}$ ${\displaystyle O_{n}}$ ${\displaystyle {\tbinom {2n-2}{n-2}}.}$ ${\displaystyle O_{n}}$ ${\displaystyle 2n-1}$

Si es un conjunto máximo independiente, formado por los conjuntos que contienen a , entonces el complemento de es el conjunto de vértices que no contienen a . Este conjunto complementario induce un emparejamiento en . Cada vértice del conjunto independiente es adyacente a vértices del emparejamiento, y cada vértice del emparejamiento es adyacente a vértices del conjunto independiente. ^[2] Debido a esta descomposición, y a que los grafos impares no son bipartitos, tienen número cromático tres: a los vértices del conjunto máximo independiente se les puede asignar un solo color, y dos colores más son suficientes para colorear el emparejamiento complementario. ${\displaystyle I}$ ${\displaystyle x}$ ${\displaystyle I}$ ${\displaystyle x}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle n-1}$

Coloración de bordes

Según el teorema de Vizing , la cantidad de colores necesarios para colorear los bordes del grafo impar es o , y en el caso del grafo de Petersen es . Cuando es una potencia de dos , la cantidad de vértices en el grafo es impar, de lo que nuevamente se deduce que la cantidad de colores de los bordes es . ^[16] Sin embargo, , , y pueden colorearse los bordes con colores. ^{[2] [16]} ${\displaystyle O_{n}}$ ${\displaystyle n}$ ${\displaystyle n+1}$ ${\displaystyle O_{3}}$ ${\displaystyle n+1}$ ${\displaystyle n}$ ${\displaystyle n+1}$ ${\displaystyle O_{5}}$ ${\displaystyle O_{6}}$ ${\displaystyle O_{7}}$ ${\displaystyle n}$

Biggs ^[9] explica este problema con la siguiente historia: once jugadores de fútbol en la ciudad ficticia de Croam desean formar parejas de equipos de cinco hombres (con un hombre sobrante para servir como árbitro) en todas las 1386 formas posibles, y desean programar los juegos entre cada pareja de tal manera que los seis juegos para cada equipo se jueguen en seis días diferentes de la semana, con domingos libres para todos los equipos. ¿Es posible hacerlo? En esta historia, cada juego representa una arista de , cada día de la semana está representado por un color, y una coloración de arista de 6 colores proporciona una solución al problema de programación de los jugadores. ${\displaystyle O_{6}}$ ${\displaystyle O_{6}}$

Hamiltonicidad

El grafo de Petersen es un grafo no hamiltoniano bien conocido , pero se sabe que todos los grafos impares para tienen un ciclo hamiltoniano . ^[17] Como los grafos impares son transitivos por vértices , son uno de los casos especiales con una respuesta positiva conocida a la conjetura de Lovász sobre ciclos hamiltonianos en grafos transitivos por vértices. Biggs ^[2] conjeturó de manera más general que las aristas de se pueden dividir en ciclos hamiltonianos disjuntos por aristas. Cuando es impar, las aristas sobrantes deben formar una correspondencia perfecta. Esta conjetura más sólida se verificó para . ^{[2] [16]} Para , el número impar de vértices en impide que exista una coloración de aristas de 8 colores, pero no descarta la posibilidad de una partición en cuatro ciclos hamiltonianos. ${\displaystyle O_{3}}$ ${\displaystyle O_{n}}$ ${\displaystyle n\geq 4}$ ${\displaystyle O_{n}}$ ${\displaystyle \lfloor n/2\rfloor }$ ${\displaystyle n}$ ${\displaystyle n=4,5,6,7}$ ${\displaystyle n=8}$ ${\displaystyle O_{n}}$

Referencias

1. Biggs, Norman L. (1976), "Gráficos automórficos y la condición de Kerin", Geometriae Dedicata , 5 (1): 117–127, doi :10.1007/BF00148146.
2. Biggs, Norman (1979), "Algunas teorías de grafos extrañas", Segunda Conferencia Internacional sobre Matemática Combinatoria, Anales de la Academia de Ciencias de Nueva York , 319 : 71–81, doi :10.1111/j.1749-6632.1979.tb32775.x.
3. West, Douglas B. (2000), "Ejercicio 1.1.28", Introducción a la teoría de grafos (2.ª ed.), Englewood Cliffs, NJ: Prentice-Hall, pág. 17.
4. Van Dam, Edwin; Haemers, Willem H. (2010), Una caracterización impar de los gráficos impares generalizados , CentER Discussion Paper Series No. 2010-47, SSRN  1596575.
5. Kowalewski, A. (1917), "Dodekaederaufgabe als Buntordnungproblem de WR Hamilton", Sitzungsber. Akád. Wiss. Viena (Abt. IIa) , 126 : 67–90, 963–1007Como lo cita Biggs (1979).
6. Balaban, Alexandru T.; Fǎrcaşiu, D.; Bǎnicǎ, R. (1966), "Gráficos de múltiples desplazamientos 1, 2 en iones de carbonio y sistemas relacionados", Rev. Roum. Chim. , 11 : 1205.
7. Balaban, Alexandru T. (1972), "Gráficos químicos, Parte XIII: Patrones combinatorios", Rev. Roumaine Math. Pures Appl. , 17 : 3–16.
8. Ghafoor, Arif; Bashkow, Theodore R. (1991), "Un estudio de gráficos impares como redes de interconexión tolerantes a fallos", IEEE Transactions on Computers , 40 (2): 225–232, doi :10.1109/12.73594.
9. Biggs, Norman (1972), Guy, Richard K. (ed.), "Un problema de coloración de aristas", Problemas de investigación, American Mathematical Monthly , 79 (9): 1018–1020, doi :10.2307/2318076, JSTOR  2318076.
10. Brouwer, Andries ; Cohen, Arjeh M.; Neumaier, A. (1989), Gráficos regulares de distancias , ISBN 0-387-50619-5.
11. Ed Pegg, Jr. (29 de diciembre de 2003), Cubic Symmetric Graphs, Math Games, Asociación Matemática de Estados Unidos , archivado desde el original el 21 de agosto de 2010 , consultado el 24 de agosto de 2010.
12. Babai, László (1995), "Grupos de automorfismo, isomorfismo, reconstrucción", en Graham, Ronald L. ; Grötschel, Martin ; Lovász, László (eds.), Handbook of Combinatorics, vol. I, North-Holland, pp. 1447–1540, Proposición 1.9, archivado desde el original el 11 de junio de 2010.
13. Moon, Aeryung (1982), "Caracterización de los gráficos impares O _k por parámetros", Matemáticas discretas , 42 (1): 91–97, doi : 10.1016/0012-365X(82)90057-7.
14. Godsil, CD (1980), "Más teoría de grafos impares", Discrete Mathematics , 32 (2): 205–207, doi : 10.1016/0012-365X(80)90055-2.
15. Watkins, Mark E. (1970), "Conectividad de grafos transitivos", Journal of Combinatorial Theory , 8 : 23–29, doi :10.1016/S0021-9800(70)80005-9, MR  0266804
16. Meredith, Guy HJ; Lloyd, E. Keith (1973), "Los futbolistas de Croam", Journal of Combinatorial Theory, Serie B , 15 (2): 161–166, doi :10.1016/0095-8956(73)90016-6.
17. Mütze, Torsten; Nummenpalo, Jerri; Walczak, Bartosz (2018), "Los gráficos de Kneser dispersos son hamiltonianos", STOC'18—Actas del 50.° Simposio anual ACM SIGACT sobre teoría de la computación , Nueva York: ACM, págs. 912–919, arXiv : 1711.01636 , MR  3826304

Enlaces externos

• Weisstein, Eric W. , "Gráfico impar", MathWorld