Gráfico extraño

Si dos vértices en${\displaystyle O_{n}}$corresponden a conjuntos que difieren entre sí por la eliminación de${\displaystyle k}$elementos de un conjunto y la adición de${\displaystyle k}$diferentes elementos, entonces se puede llegar a ellos entre sí en${\displaystyle 2k}$pasos, cada par de los cuales realiza una única suma y una eliminación. Si${\displaystyle 2k<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 al segundo, y luego llegar al segundo conjunto en un paso más. Por lo tanto, el diámetro de${\displaystyle O_{n}}$es${\displaystyle n-1}$. ^{[ 1 ] [ 2 ]}

Todo grafo impar es 3-arco-transitivo : todo camino dirigido de tres aristas en un grafo impar puede transformarse en cualquier otro camino de este tipo mediante 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, están definidos de forma única por su matriz de intersección: 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${\displaystyle O_{n}}$para${\displaystyle n>2}$nunca son grafos de Cayley . ^{[ 14 ]}

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

Gráficos extraños con${\displaystyle n>3}$tienen circunferencia seis; sin embargo, aunque no son grafos bipartitos , sus ciclos impares son mucho más largos. Específicamente, el grafo impar${\displaystyle O_{n}}$tiene una circunferencia extraña${\displaystyle 2n-1}$. Si un${\displaystyle n}$-El gráfico regular tiene diámetro${\displaystyle n-1}$y circunferencia extraña${\displaystyle 2n-1}$y solo tiene${\displaystyle n}$valores propios distintos , debe ser distancia-regular. Gráficos distancia-regulares con diámetro${\displaystyle n-1}$y circunferencia extraña${\displaystyle 2n-1}$se conocen como grafos impares generalizados , e incluyen los grafos de cubo plegado , así como los propios grafos impares. ^{[ 4 ]}

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

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

Según el teorema de Vizing , el número de colores necesarios para colorear las aristas del grafo impar es...${\displaystyle O_{n}}$es o${\displaystyle n}$o${\displaystyle n+1}$y en el caso del gráfico de Petersen${\displaystyle O_{3}}$es${\displaystyle n+1}$. Cuando${\displaystyle n}$es una potencia de dos , el número de vértices en el grafo es impar, de lo cual se deduce nuevamente que el número de colores de aristas es${\displaystyle n+1}$. ^{[ 16 ]} Sin embargo,${\displaystyle O_{5}}$,${\displaystyle O_{6}}$, y${\displaystyle O_{7}}$cada uno puede tener los bordes coloreados con${\displaystyle n}$colores. ^{[ 2 ] [ 16 ]}

Biggs ^{[ 9 ]} explica este problema con la siguiente historia, sobre los "futbolistas de Croam": once jugadores de fútbol en la ciudad ficticia de Croam desean formar parejas de equipos de cinco hombres (con un hombre sobrante que servirá como árbitro) de las 1386 maneras posibles, y desean programar los partidos entre cada pareja de tal manera que los seis partidos 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 partido representa un borde de${\displaystyle O_{6}}$, cada día de la semana está representado por un color y un coloreado de borde de 6 colores${\displaystyle O_{6}}$Proporciona una solución al problema de la programación de los jugadores.

El gráfico de Petersen${\displaystyle O_{3}}$es un grafo no hamiltoniano bien conocido , pero todos los grafos impares${\displaystyle O_{n}}$para${\displaystyle n\geq 4}$Se sabe que tienen un ciclo hamiltoniano . ^{[ 17 ]} Como los grafos impares son transitivos en 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 en vértices. Biggs ^{[ 2 ]} conjeturó de manera más general que las aristas de${\displaystyle O_{n}}$se puede dividir en${\displaystyle \lfloor n/2\rfloor }$Ciclos hamiltonianos disjuntos en aristas. Cuando${\displaystyle n}$es extraño, los bordes restantes deben entonces formar un emparejamiento perfecto. Esta conjetura más fuerte fue verificada para${\displaystyle n=4,5,6,7}$. ^{[ 2 ] [ 16 ]} Para${\displaystyle n=8}$, el número impar de vértices en${\displaystyle O_{n}}$impide que exista una coloración de bordes de 8 colores, pero no descarta la posibilidad de una partición en cuatro ciclos hamiltonianos.