La hipótesis de Vizing

La conjetura de Vizing  es una suposición sobre la conexión entre el conjunto dominante y el producto directo de los gráficos , que no se ha confirmado hasta 2017, mientras que la hipótesis se ha probado para varios casos especiales.

Fue expresado por primera vez por Vadim Vizing [1] . El enunciado de la hipótesis dice que para  el mínimo número de vértices en el conjunto dominante del grafo , tenemos:

.

En 1995 [2] , se propusieron límites similares para el número dominante del producto tensorial de grafos , pero más tarde [3] se encontró un contraejemplo.

Ejemplos

El número dominante de un ciclo con 4 vértices C 4 es dos: cualquier vértice único se domina a sí mismo y a dos vecinos, pero cualquier par domina el gráfico completo. El producto C 4 ◻ C 4 es un gráfico de hipercubo de cuatro dimensiones . Tiene 16 vértices, y cualquier vértice individual se domina a sí mismo y a cuatro vecinos, por lo que tres vértices solo pueden dominar 15 de los 16 vértices. Por lo tanto, al menos cuatro vértices deben estar contenidos en el conjunto dominante del gráfico, justo el número dado por la conjetura de Vizing.

El número dominante del producto puede ser mucho mayor que el límite dado en la conjetura de Vizing. Por ejemplo, para una estrella K 1, n , el número dominante γ(K 1, n ) es igual a uno: solo un vértice central domina todo el gráfico. Para un gráfico G = K 1, n ◻ K 1, n , formado por el producto de dos estrellas, la conjetura de Vizing establece que el número dominante es al menos 1 × 1 = 1. Sin embargo, de hecho, el conjunto dominante es mucho más grande El gráfico contiene n 2 + 2 n + 1 vértices: n 2 se obtiene de las hojas de dos factores, 2 n se obtiene del producto de las hojas y el centro, y un vértice se obtiene del producto de los centros. Cada producto de centro de hoja domina exactamente n vértices de hoja a hoja del producto, por lo que se necesitan n vértices de centro de hoja para dominar todos los vértices de hoja a hoja. Sin embargo, ningún vértice del centro de la hoja domina al mismo otro vértice, por lo que incluso si se eligen n vértices del centro de la hoja como conjunto dominante, hay n vértices del centro de la hoja no dominados que están dominados por un vértice del centro de la hoja. Por lo tanto, el número dominante de este gráfico es γ(K 1, n ◻ K 1, n ) = n + 1, que es mucho mayor que el límite trivial dado por la conjetura de Vizing.

Existe una familia infinita de productos gráficos para los que la estimación en la conjetura de Vizing es nítida [4] [5] [6] [7] . Por ejemplo, si G y H son gráficos conectados y cada uno tiene al menos cuatro vértices y el número de vértices es exactamente el doble del número dominante, entonces γ( G ◻ H ) = γ( G )γ( H ) [8] . Los gráficos G y H con esta propiedad contienen un ciclo C 4 con cuatro vértices junto con el producto raíz de un gráfico conexo y un solo borde [8] .

Resultados parciales

Está claro que la conjetura se cumple cuando G o H tienen un número dominante 1: el producto contiene una copia isomorfa del segundo, de modo que su conjunto dominante tiene al menos vértices γ( G )γ( H ).

Se sabe que la conjetura de Vizing se cumple para ciclos [6] [9] y para gráficos con el número dos dominante [10] .

En 2000 [11] se demostró que el número dominante del producto es al menos igual a la mitad del límite especificado en la conjetura para todo G y H.

Límites superiores

Vizing en el artículo original [1] señaló que:

γ( GRAMO ◻ H ) ≤ min{γ( GRAMO )|V( H )|, γ( H )|V( GRAMO )|}.

El conjunto dominante que alcanza este límite se puede obtener como un producto directo de los conjuntos dominantes de uno de los gráficos G o H con el conjunto de todos los vértices del otro gráfico.

Notas

  1. ↑ 1 2 Vising, 1968 .
  2. ↑ Gravier, Khelladi, 1995 .
  3. ↑ Klavžar, Zmazek, 1996 .
  4. ↑ Payán, Xuong, 1982 .
  5. ↑ Fink, Jacobson, Kinch, Roberts, 1985 .
  6. ↑ 12 Jacobson , Kinch, 1986 .
  7. ↑ Hartnell, Rall, 1991 .
  8. ↑ 1 2 Fink, Jacobson, Kinch, Roberts, 1985 .
  9. ↑ El-Zahar, Pareek, 1991 .
  10. ↑ Bartsalkin, alemán, 1979 .
  11. ↑ Clark, Suen, 2000 .

Literatura

Enlaces