La conjetura de Vizing

Problema sin resolver en matemáticas

Conjetura:${\displaystyle \gamma (G\,\Box \,H)\geq \gamma (G)\gamma (H)\,}$

Más problemas sin resolver en matemáticas

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 el grafo G , entonces 

${\displaystyle \gamma (G\,\Box \,H)\geq \gamma (G)\gamma (H).\,}$

Gravier y Khelladi (1995) conjeturaron una cota similar para el número de dominación del producto tensorial de grafos ; sin embargo, Klavžar y Zmazek (1996) hallaron 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 una visión general más detallada de estos resultados, véase Brešar et al. (2012) .

Un ciclo de 4 _vértices C₄ tiene dominación 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 grafo. El producto _C₄ □ C₄ es un 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 podrían dominar 15 de los 16 vértices. Por lo tanto, se requieren al menos cuatro vértices para dominar todo el grafo, 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 grafo G = K _{1, n} □ K _{1, n} formado como el producto de dos estrellas, la conjetura de Vizing solo afirma que el número de dominación debe ser al menos 1 × 1 = 1 . Sin embargo, el número de dominación de este grafo es en realidad mucho mayor. Tiene n ² + 2 n + 1 vértices: n ² formados a partir del producto de una hoja en ambos factores, 2 n a partir del producto de una hoja en un factor y el centro en el otro factor, y un vértice restante formado a partir del producto de los dos centros. Cada vértice de producto hoja-centro en G domina exactamente n de los vértices hoja-hoja, por lo que se necesitan n vértices hoja-centro para dominar todos los vértices hoja-hoja. Sin embargo, ningún vértice hoja-centro domina a ningún otro vértice de este tipo, por lo que incluso después de elegir n vértices hoja-centro para incluirlos en el conjunto dominante, quedan n más vértices hoja-centro no dominados, que pueden ser dominados por el único vértice centro-centro. Por lo tanto, el número de dominación de este grafo es γ( K _{1, n} □ K _{1, n} ) = n + 1 mucho mayor que la cota trivial de uno dada por la conjetura de Vizing.

Existen familias infinitas de productos de grafos para las cuales se cumple exactamente la cota de la conjetura de Vizing. ^{[ 1 ]} Por ejemplo, si G y H son grafos conexos, cada uno con al menos cuatro vértices y con un número total de vértices exactamente el doble de su número de dominación, entonces γ( G □ H ) = γ( G ) γ( H ) . ^{[ 2 ]} Los grafos G y H con esta propiedad consisten en el ciclo de cuatro vértices C ₄ junto con los productos enraizados de un grafo conexo y una sola arista. ^{[ 2 ]}

Claramente, la conjetura se cumple cuando G o H tienen número de dominación uno: porque el producto contiene una copia isomorfa del otro factor, cuya dominación requiere al menos γ( G )γ( H ) vértices.

También se sabe que la conjetura de Vizing es válida para ciclos ^{[ 3 ]} y para grafos con número de dominación dos. ^{[ 4 ]}

Clark y Suen (2000) demostraron que el número de dominación del producto es al menos la mitad de grande que el límite conjeturado, para todo G y H.

Vizing (1968) observó que

${\displaystyle \gamma (G\,\Box \,H)\leq \min\{\gamma (G)|V(H)|,\gamma (H)|V(G)|\}.}$

Un conjunto dominante que cumpla con este límite puede formarse como el producto cartesiano de un conjunto dominante en uno de los grafos G o H con el conjunto de todos los vértices en el otro grafo.

• Weisstein, Eric W. "Conjetura de Vizing" . MathWorld .