En teoría de grafos , la conjetura de Vizing se refiere a una relación entre el número de dominación y el producto cartesiano de grafos . Esta conjetura fue enunciada por primera vez por Vadim G. Vizing ( 1968 ), y establece que, si γ ( G ) denota el número mínimo de vértices en un conjunto dominante para G , entonces
Gravier y Khelladi (1995) conjeturaron un límite similar para el número de dominación del producto tensorial de las gráficas ; sin embargo, Klavžar y Zmazek (1996) encontraron un contraejemplo . Desde que Vizing propuso su conjetura, muchos matemáticos han trabajado en ella, con resultados parciales que se describen a continuación. Para obtener una descripción más detallada de estos resultados, consulte Brešar et al. (2012) .
Ejemplos de
Un C 4 de 4 ciclos tiene el dominio número dos: cualquier vértice solo se domina a sí mismo y a sus dos vecinos, pero cualquier par de vértices domina todo el gráfico. El productoes un gráfico hipercubo de cuatro dimensiones ; tiene 16 vértices, y cualquier vértice solo puede dominarse 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, se requieren al menos cuatro vértices para dominar todo el gráfico, el límite dado por la conjetura de Vizing.
Es posible que el número de dominación de un producto sea mucho mayor que el límite dado por la conjetura de Vizing. Por ejemplo, para una estrella K 1, n , su número de dominación γ (K 1, n ) es uno: es posible dominar toda la estrella con un solo vértice en su centro. Por lo tanto, para el gráficoformado como el producto de dos estrellas, la conjetura de Vizing establece solo que el número de dominación debe ser al menos 1 × 1 = 1. Sin embargo, el número de dominación de este gráfico es en realidad mucho mayor. Tiene n 2 + 2 n + 1 vértices: n 2 formado a partir del producto de una hoja en ambos factores, 2 n del producto de una hoja en un factor y el eje en el otro factor, y un vértice restante formado a partir del producto de los dos ejes. Cada vértice del producto del eje de la hoja en G domina exactamente n de los vértices hoja-hoja, por lo que se necesitan n vértices del eje de la hoja para dominar todos los vértices hoja-hoja. Sin embargo, ningún vértice del eje de la hoja domina a ningún otro vértice de este tipo, por lo que incluso después de que se elijan n vértices de eje de hoja para incluirlos en el conjunto dominante, quedan n más vértices de eje de hoja no dominados, que pueden ser dominados por el eje único. vértice del eje. Por lo tanto, el número de dominación de este gráfico es mucho más alto que el límite trivial de uno dado por la conjetura de Vizing.
Existen infinitas familias de productos gráficos para los que se cumple exactamente el límite de la conjetura de Vizing. [1] Por ejemplo, si G y H son gráficos conectados, cada uno con al menos cuatro vértices y exactamente el doble de vértices totales que sus números de dominación, entonces. [2] Las gráficas G y H con esta propiedad consisten en el ciclo de cuatro vértices C 4 junto con los productos con raíces de una gráfica conectada y un solo borde. [2]
Resultados parciales
Claramente, la conjetura es válida cuando G o H tienen el dominio número uno: porque, el producto contiene una copia isomórfica del otro factor, el dominio que requiere al menos γ ( G ) γ ( H ) vértices.
También se sabe que la conjetura de Vizing es válida para ciclos [3] y para gráficos con dominación número dos. [4]
Clark y Suen (2000) demostraron que el número dominación del producto es al menos la mitad tan grande como la conjeturado obligado, para todos G y H .
Límites superiores
Vizing (1968) observó que
Un conjunto dominante que cumpla con este límite puede formarse como el producto cartesiano de un conjunto dominante en uno de G o H con el conjunto de todos los vértices en el otro gráfico.
Notas
Referencias
- Barcalkin, AM; Alemán, LF (1979), "El número de estabilidad externa del producto cartesiano de gráficos", Bul. Akad. Stiince RSS Moldoven (en ruso), 1 : 5–8, MR 0544028.
- Brešar, Boštjan; Dorbec, Paul; Goddard, Wayne; Hartnell, Bert L .; Henning, Michael A .; Klavžar, Sandi; Rall, Douglas F. (2012), "Conjetura de Vizing: una encuesta y resultados recientes", Journal of Graph Theory , 69 (1): 46–76, doi : 10.1002 / jgt.20565 , MR 2864622.
- Clark, W. Edwin; Suen, Stephen (2000), "Desigualdad relacionada con la conjetura de Vizing" , Electronic Journal of Combinatorics , 7 (1): N4, MR 1763970.
- El-Zahar, M .; Pareek, CM (1991), "Número de dominación de productos de gráficos", Ars Combin. , 31 : 223–227, MR 1110240.
- Fink, JF; Jacobson, MS; Kinch, LF; Roberts, J. (1985), "Sobre gráficos que tienen un número de dominación la mitad de su orden", Period. Matemáticas. Hungar. , 16 (4): 287–293, doi : 10.1007 / BF01848079 , MR 0833264.
- Gravier, S .; Khelladi, A. (1995), "Sobre el número de dominación de los productos cruzados de los gráficos", Matemáticas discretas , 145 : 273–277, doi : 10.1016 / 0012-365X (95) 00091-A , MR 1356600.
- Hartnell, BL; Rall, DF (1991), "Sobre la conjetura de Vizing", Congr. Numer. , 82 : 87–96, MR 1152060.
- Jacobson, MS; Kinch, LF (1986), "Sobre el dominio de los productos de los gráficos II: árboles", J. Graph Theory , 10 : 97–106, doi : 10.1002 / jgt.3190100112 , MR 0830061.
- Klavžar, Sandi; Zmazek, B. (1996), "Sobre una conjetura similar a Vizing para gráficos de productos directos", Matemáticas discretas , 156 : 243–246, doi : 10.1016 / 0012-365X (96) 00032-5 , MR 1405022.
- Payan, C .; Xuong, NH (1982), "Gráficos equilibrados por dominación", J. Graph Theory , 6 : 23–32, doi : 10.1002 / jgt.3190060104 , MR 0644738.
- Vizing, VG (1968), "Algunos problemas no resueltos en teoría de grafos", Uspekhi Mat. Nauk (en ruso), 23 (6): 117-134, MR 0240000.
enlaces externos
- Weisstein, Eric W. "Conjetura de Vizing" . MathWorld .