En el campo matemático de la teoría de grafos , los grafos impares O n son una familia de grafos simétricos con una circunferencia impar alta , definida a partir de ciertos sistemas de conjuntos . Incluyen y generalizan el gráfico de Petersen .
Gráfico impar | |
---|---|
Vértices | |
Bordes | |
Diámetro | n - 1 [1] [2] |
Circunferencia | 3 si n = 2 5 si n = 3 6 si n > 3 [3] |
Propiedades | Transitivo a distancia |
Notación | O n |
Tabla de gráficos y parámetros |
Definición y ejemplos
El gráfico impar O n tiene un vértice para cada uno de los ( n - 1) subconjuntos -elemento de un (2 n - 1) conjunto -elemento. Dos vértices están conectados por un borde si y solo si los subconjuntos correspondientes están separados . [4] Es decir, O n es el gráfico de Kneser KG (2 n - 1, n - 1).
O 2 es un triángulo, mientras que O 3 es el conocido gráfico de Petersen .
Los gráficos impares generalizados se definen como gráficos de distancia regular con diámetro n - 1 y circunferencia impar 2 n - 1 para algunos n . [5] Incluyen los gráficos impares y los gráficos de cubos plegados .
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 O 4 . [2] [6] Los gráficos impares se han estudiado por sus aplicaciones en la teoría de gráficos químicos , en el modelado de los cambios de iones de carbonio . [7] [8] También se han propuesto como topología de red en computación paralela . [9]
La notación O n para estos gráficos fue introducida por Norman Biggs en 1972. [10] 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 de X que es el " hombre impar ", es decir, no es un miembro de ninguno de los subconjuntos asociados con los vértices incidentes a ese borde. [11] [12]
Propiedades
El gráfico impar O n es regular de grado n . Tiene vértices y bordes. Por lo tanto, el número de vértices para n = 1, 2, ... es
Distancia y simetría
Si dos vértices en O n corresponden a conjuntos que se diferencian entre sí por la eliminación de k elementos de un conjunto y la adición de k elementos diferentes, entonces pueden alcanzarse entre sí en 2 k pasos, cada par de los cuales realiza una única adición y eliminación. Si 2 k < n , este es el camino más corto ; de lo contrario, es más corto encontrar un camino de este tipo desde el primer conjunto a un conjunto complementario del segundo, y luego llegar al segundo conjunto en un paso más. Por lo tanto, el diámetro de O n es n - 1. [1] [2]
Cada gráfico impar es transitivo de 3 arcos : cada camino de tres bordes dirigido en un gráfico impar se puede transformar en cualquier otro camino mediante una simetría del gráfico. [13] Los gráficos impares son transitivos a la distancia , por lo tanto, la distancia es regular . [2] Como gráficos de distancia regular, se definen de forma única 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 de su alto grado de simetría, los gráficos impares O n para n > 2 nunca son gráficos de Cayley . [15]
Debido a que los gráficos impares son regulares y transitivos por aristas , su conectividad de vértice es igual a su grado, n . [dieciséis]
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. En concreto, el gráfico impar O n tiene impar circunferencia 2 n - 1. Si un n gráfico -regular tiene diámetro n - 1 y la circunferencia impar 2 n - 1, y sólo tiene n distintos valores propios , que debe ser a distancia regular. Las gráficas de distancia regular con diámetro n - 1 y circunferencia impar 2 n - 1 se conocen como gráficas impares generalizadas e incluyen las gráficas de cubo plegado así como las gráficas impares en sí mismas. [5]
Conjuntos independientes y coloración de vértices
Deje O n ser un gráfico impar definida a partir de los subconjuntos de un (2 n - 1) conjunto -elemento X , y dejar que x ser cualquier miembro de X . Entonces, entre los vértices de O n , exactamentelos vértices corresponden a conjuntos que contienen x . Como todos estos conjuntos contienen x , no son disjuntos y forman un conjunto independiente de O n . Es decir, O n tiene 2 n - 1 conjuntos de tamaño independientes diferentes. Se deduce del teorema de Erdős-Ko-Rado que estos son los conjuntos máximos independientes de O n . es decir, el número de independencia de O n esAdemás, cada conjunto máximo independiente debe tener esta forma, por lo que O n tiene exactamente 2 n - 1 conjuntos máximos independientes. [2]
Si I es un conjunto máximo independiente, formado por los conjuntos que contienen x , entonces el complemento de I es el conjunto de vértices que no contienen x . Este conjunto complementario induce una coincidencia en G . Cada vértice del conjunto independiente es adyacente a n vértices del emparejamiento, y cada vértice del emparejamiento es adyacente a n - 1 vértices del conjunto independiente. [2] Debido a esta descomposición, y debido a que los gráficos impares no son bipartitos, tienen el 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 la coincidencia complementaria.
Coloración de bordes
Según el teorema de Vizing , el número de colores necesarios para colorear los bordes del gráfico impar O n es n o n + 1, y en el caso del gráfico de Petersen O 3 es n + 1. Cuando n es una potencia de dos , el número de vértices en el gráfico es impar, de lo cual se sigue nuevamente que el número de colores de borde es n + 1. [17] Sin embargo, O 5 , O 6 y O 7 pueden tener cada uno un color de borde con n colores . [2] [17]
Biggs [10] 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 impar para servir como árbitro) de todas las 1386 formas posibles, y Desea programar los juegos entre cada pareja de tal manera que los seis juegos de cada equipo se jueguen en seis días diferentes de la semana, con los domingos libres para todos los equipos. ¿Es posible hacerlo? En esta historia, cada juego representa un borde de O 6 , cada día de la semana está representado por un color y un color de borde de 6 colores de O 6 proporciona una solución al problema de programación de los jugadores.
Hamiltonicidad
El gráfico de Petersen O 3 es un gráfico no hamiltoniano bien conocido, pero se sabe que todos los gráficos impares O n para n ≥ 4 tienen un ciclo hamiltoniano. [18] Como los gráficos impares son transitivos de vértice , son uno de los casos especiales para los que se conoce una respuesta positiva a la conjetura de Lovász . Biggs [2] conjeturó de manera más general que los bordes de O n se pueden dividir enciclos hamiltonianos de bordes disjuntos. Cuando n es impar, los bordes sobrantes deben formar una combinación perfecta. Esta conjetura más fuerte se verificó para n = 4, 5, 6, 7. [2] [17] Para n = 8, el número impar de vértices en O n evita que exista una coloración de borde de 8 colores, pero no descarta la posibilidad de una partición en cuatro ciclos hamiltonianos.
Referencias
- ^ a b Biggs, Norman L. (1976), "Gráficos automórficos y la condición de Kerin", Geometriae Dedicata , 5 (1): 117-127, doi : 10.1007 / BF00148146.
- ^ a b c d e f g h yo Biggs, Norman (1979), "Alguna teoría de grafos impares", Segunda Conferencia Internacional sobre Matemáticas Combinatorias, Anales de la Academia de Ciencias de Nueva York , 319 : 71–81, doi : 10.1111 / j.1749-6632.1979.tb32775.x.
- ^ West, Douglas B. (2000), "Ejercicio 1.1.28", Introducción a la teoría de grafos (2ª ed.), Englewood Cliffs, Nueva Jersey: Prentice-Hall, p. 17.
- ^ Weisstein, Eric W. "Gráfico impar" . MathWorld .
- ^ a b Van Dam, Edwin; Haemers, Willem H. (2010), An Odd Characterization of the Generalized Odd Graphs , CentER Discussion Paper Series No. 2010-47, SSRN 1596575.
- ^ Kowalewski, A. (1917), "WR Hamilton's Dodekaederaufgabe als Buntordnungproblem", Sitzungsber. Akad. Wiss. Viena (Abt. IIa) , 126 : 67–90, 963–1007. Como lo cita Biggs (1979) .
- ^ 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.
- ^ Balaban, Alexandru T. (1972), "Gráficos químicos, Parte XIII: Patrones combinatorios", Rev. Roumaine Math. Puras Appl. , 17 : 3-16.
- ^ Ghafoor, Arif; Bashkow, Theodore R. (1991), "Un estudio de gráficos impares como redes de interconexión tolerantes a fallas", IEEE Transactions on Computers , 40 (2): 225-232, doi : 10.1109 / 12.73594.
- ^ a b Biggs, Norman (1972), Guy, Richard K. (ed.), "An edge-coloring problem", Research Problems, American Mathematical Monthly , 79 (9): 1018–1020, doi : 10.2307 / 2318076 , JSTOR 2318076.
- ^ Brouwer, Andries ; Cohen, Arjeh M .; Neumaier, A. (1989), Gráficos regulares a distancia , ISBN 0-387-50619-5.
- ^ Ed Pegg, Jr. (29 de diciembre de 2003), Cubic Symmetric Graphs , Math Games, Mathematical Association of America , archivado desde el original el 21 de agosto de 2010 , recuperado el 24 de agosto de 2010.
- ^ 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 , I , North-Holland, págs. 1447-1540, Proposición 1.9, archivado desde el original el 11 de junio de 2010.
- ^ 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.
- ^ Godsil, CD (1980), "Teoría de grafos más impares", Matemáticas discretas , 32 (2): 205-207, doi : 10.1016 / 0012-365X (80) 90055-2.
- ^ Watkins, Mark E. (1970), "Conectividad de gráficos transitivos", Journal of Combinatorial Theory , 8 : 23-29, doi : 10.1016 / S0021-9800 (70) 80005-9 , MR 0266804
- ^ a b c Meredith, Guy HJ; Lloyd, E. Keith (1973), "The footballers of Croam", Journal of Combinatorial Theory, Serie B , 15 (2): 161-166, doi : 10.1016 / 0095-8956 (73) 90016-6.
- ^ Mütze, Torsten; Nummenpalo, Jerri; Walczak, Bartosz (2018), "Sparse Kneser graphs are hamiltonian", STOC'18 — Actas del 50º Simposio Anual de ACM SIGACT sobre Teoría de la Computación , Nueva York: ACM, págs. 912–919, arXiv : 1711.01636 , MR 3826304