En teoría de grafos, el grafo de Kneser (alternativamente ) es el grafo cuyos vértices corresponden a los subconjuntos de elementos de un conjunto de elementos, y donde dos vértices son adyacentes si y solo si los dos correspondientes conjuntos son disjuntos. Los grafos de Kneser llevan el nombre de Martin Kneser, quien los investigó por primera vez en 1956.
Ejemplos
El grafo de Kneser es el grafo completo de vértices.
El grafo de Kneser es el complemento del grafo línea del grafo completo sobre vértices.
El grafo de Kneser es el grafo impar ; en particular, es el grafo de Petersen (véase la figura de la parte superior derecha).
El grafo de Kneser , visualizado a la derecha.
Propiedades
Propiedades básicas El grafo de Kneser tiene vértices. Cada vértice tiene exactamente vecinos. El grafo de Kneser es transitivo de vértices y arco transitivo. Cuando , el grafo de Kneser es un grafo fuertemente regular, con parámetros . Sin embargo, no es muy regular cuando , ya que diferentes pares de vértices no adyacentes tienen diferentes números de vecinos comunes según el tamaño de la intersección de los correspondientes pares de conjuntos. Debido a que los grafos de Kneser son regulares y transitivo de vínculos, su conectividad de vértices es igual a su grado, excepto por que está desconectado. Más precisamente, la conectividad de es igual al número de vecinos por vértice .
Número cromático Como conjeturó , el coloreado del grafo de Kneser para es exactamente . Por ejemplo, el grafo de Petersen requiere tres colores en cualquier coloración propia. Esta conjetura se ha demostrado de varias maneras.
demostró esto utilizando métodos topológicos, dando lugar al campo de la combinatoria topológica. Poco tiempo después, dio una prueba simple, usando el teorema de Borsuk-Ulam y un lema de David Gale. ganó el premio Morgan por una prueba aún más simplificada pero todavía topológica. encontró una prueba combinatoria puramente. Cuando , el número cromático de es 1.
Ciclo hamiltoniano El grafo de Kneser contiene un camino hamiltoniano si :
Ya que
válido para todo k. Esta condición se cumple si
El grafo de Kneser contiene un ciclo hamiltoniano si existe un entero no negativo a tal que . En particular, el grafo impar tiene un ciclo hamiltoniano si . Con la excepción del grafo de Petersen, todos los grafos de Kneser conectados con son hamiltonianos .
Cliques Cuando , el grafo de Kneser no contiene triángulos. De manera más general, cuando no contiene cliques de tamaño , mientras que contiene tales cliques cuando . Además, aunque el grafo de Kneser siempre contiene ciclos de longitud cuatro siempre que , para valores de cercanos a , el ciclo impar más corto puede tener una longitud variable .
Diámetro El diámetro de un grafo de Kneser conectado es :
Espectro El espectro del grafo de Kneser consta de k + 1 autovalores distintos:
Además aparece con multiplicidad para y tiene multiplicidad 1.
Número de independencia El teorema Erdős-Ko-Rado establece que el conjunto independiente del grafo de Kneser para es
Grafos relacionados El grafo de Johnson es aquel cuyos vértices son los subconjuntos de elementos de un conjunto de elementos, siendo dos vértices adyacentes cuando se encuentran en un conjunto de elementos. El grafo de Johnson es el complemento del grafo de Kneser . Los grafos de Johnson están estrechamente relacionados con el esquema de Johnson, que llevan el nombre de Selmer M. Johnson.
El grafo de Kneser generalizado tiene el mismo conjunto de vértices que el grafo de Kneser , pero conecta dos vértices siempre que correspondan a conjuntos que se cruzan en o menos elementos . Así .
El grafo de Kneser bipartito tiene como vértices los conjuntos de y de elementos extraídos de una colección de elementos. Dos vértices están conectados por una arista siempre que un conjunto es un subconjunto del otro. Al igual que el grafo de Kneser, es vértice transitivo con grado . El grafo de Kneser bipartito se puede formar como un recubrimiento doble bipartito de en el que se hacen dos copias de cada vértice y se reemplaza cada vínculo por un par de vínculos que conectan los correspondientes pares de vértices . El grafo de Kneser bipartito es el grafo de Desargues y el grafo de Kneser bipartito es un grafo en corona.
Referencias
Bibliografía
Enlaces externos
Categoría:Familias paramétricas de grafos Categoría:Grafos regulares