stringtranslate.com

Gráfica de Kneser

En teoría de grafos , el grafo de Kneser K ( n , k ) (alternativamente KG n , k ) es el grafo cuyos vértices corresponden a los subconjuntos de k elementos de un conjunto de n elementos , y donde dos vértices son adyacentes si y solo si los dos conjuntos correspondientes son disjuntos . Los grafos de Kneser reciben su nombre de Martin Kneser , quien los investigó por primera vez en 1956.

Ejemplos

Gráfica de Kneser O 4 = K (7, 3)

El grafo de Kneser K ( n , 1) es el grafo completo en n vértices.

El grafo de Kneser K ( n , 2) es el complemento del grafo lineal del grafo completo en n vértices.

El gráfico de Kneser K (2 n − 1, n − 1) es el gráfico impar O n ; en particular O 3 = K (5, 2) es el gráfico de Petersen (ver la figura superior derecha).

El gráfico de Kneser O 4 = K (7, 3) , visualizado a la derecha.

Propiedades

Propiedades básicas

El gráfico de Kneser tiene vértices. Cada vértice tiene exactamente vecinos.

El grafo de Kneser es transitivo por vértices y transitivo por arcos . Cuando , el grafo de Kneser es un grafo fuertemente regular , con parámetros . Sin embargo, no es fuertemente regular cuando , ya que diferentes pares de vértices no adyacentes tienen diferentes números de vecinos comunes dependiendo del tamaño de la intersección de los pares de conjuntos correspondientes.

Debido a que los grafos de Kneser son regulares y transitivos en sus aristas , su conectividad de vértices es igual a su grado , excepto que está desconectado . Más precisamente, la conectividad de es la misma que el número de vecinos por vértice. [1]

Número cromático

Como conjeturó Kneser (1956) , el número cromático del gráfico de Kneser para es exactamente n − 2 k + 2 ; por ejemplo, el gráfico de Petersen requiere tres colores en cualquier coloración adecuada . Esta conjetura se demostró de varias maneras.

Por el contrario, el número cromático fraccionario de estos grafos es . [6] Cuando , no tiene aristas y su número cromático es 1.

Ciclos hamiltonianos

Es bien sabido que el gráfico de Petersen no es hamiltoniano , pero durante mucho tiempo se conjeturó que esta era la única excepción y que cualquier otro gráfico de Kneser conexo K ( n , k ) es hamiltoniano.

En 2003, Chen demostró que el gráfico de Kneser K ( n , k ) contiene un ciclo hamiltoniano si [7]

Desde

se cumple para todos , esta condición se cumple si

Casi al mismo tiempo, Shields demostró (computacionalmente) que, excepto el gráfico de Petersen, todos los gráficos de Kneser conectados K ​​( n , k ) con n ≤ 27 son hamiltonianos. [8]

En 2021, Mütze, Nummenpalo y Walczak demostraron que el grafo de Kneser K ( n , k ) contiene un ciclo hamiltoniano si existe un entero no negativo tal que . [9] En particular, el grafo impar O n tiene un ciclo hamiltoniano si n ≥ 4 . Finalmente, en 2023, Merino, Mütze y Namrata completaron la prueba de la conjetura. [10]

Camarillas

Cuando n < 3 k , el grafo de Kneser K ( n , k ) no contiene triángulos. En términos más generales, cuando n < ck no contiene camarillas de tamaño c , mientras que sí contiene dichas camarillas cuando nck . Además, aunque el grafo de Kneser siempre contiene ciclos de longitud cuatro siempre que n ≥ 2 k + 2 , para valores de n cercanos a 2 k el ciclo impar más corto puede tener longitud variable. [11]

Diámetro

El diámetro de un grafo de Kneser conexo K ( n , k ) es [12]

Espectro

El espectro del grafo de Kneser K ( n , k ) consta de k + 1 valores propios distintos : Además ocurre con multiplicidad para y tiene multiplicidad 1. [13]

Número de independencia

El teorema de Erdős–Ko–Rado establece que el número de independencia del grafo de Kneser K ( n , k ) para es

Gráficos relacionados

El grafo de Johnson J ( n , k ) es el grafo cuyos vértices son los subconjuntos de k elementos de un conjunto de n elementos, siendo dos vértices adyacentes cuando se encuentran en un conjunto de ( k  − 1) elementos. El grafo de Johnson J ( n , 2) es el complemento del grafo de Kneser K ( n , 2) . Los grafos de Johnson están estrechamente relacionados con el esquema de Johnson , ambos nombrados en honor a Selmer M. Johnson .

El gráfico de Kneser generalizado K ( n , k , s ) tiene el mismo conjunto de vértices que el gráfico de Kneser K ( n , k ) , pero conecta dos vértices siempre que correspondan a conjuntos que se intersecan en s o menos elementos. [11] Por lo tanto, K ( n , k , 0) = K ( n , k ) .

El grafo bipartito de Kneser H ( n , k ) tiene como vértices los conjuntos de k y nk elementos extraídos de una colección de n elementos. Dos vértices están conectados por una arista siempre que un conjunto sea un subconjunto del otro. Al igual que el grafo de Kneser, es transitivo en vértices con grado El grafo bipartito de Kneser se puede formar como una doble cubierta bipartita de K ( n , k ) en la que se hacen dos copias de cada vértice y se reemplaza cada arista por un par de aristas que conectan pares correspondientes de vértices. [14] El grafo bipartito de Kneser H (5, 2) es el grafo de Desargues y el grafo bipartito de Kneser H ( n , 1) es un grafo de corona .

Referencias

Notas

  1. ^ Villanueva (1970).
  2. ^ Lovász (1978).
  3. ^ Bárány (1978).
  4. ^ Verde (2002).
  5. ^ Matoušek (2004).
  6. ^ Godsil y Meagher (2015).
  7. ^ Chen (2003).
  8. ^ Escudos (2004).
  9. ^ Mütze, Nummenpalo y Walczak (2021).
  10. ^ Merino, Mütze y Namrata (2023).
  11. ^ por Denley (1997).
  12. ^ Valencia-Pabón y Vera (2005).
  13. ^ "Copia archivada" (PDF) . www.math.caltech.edu . Archivado desde el original (PDF) el 23 de marzo de 2012 . Consultado el 9 de agosto de 2022 .{{cite web}}: CS1 maint: archived copy as title (link)
  14. ^ Simpson (1991).

Obras citadas

Enlaces externos