¿Es esto un contraejemplo a una conjetura sobre la dominación independiente en productos de grafos cartesianos?

Question

LA CONJURACIÓN DE VIZING: UN ESTUDIO Y RESULTADOS RECIENTES (2009) por Bostjan Bresar , Paul Dorbec , Wayne Goddard , Bert L. Hartnell , Michael A. Henning , Sandi Klavzar , Douglas F. Rall p.25:

Conjetura 9.6. Para todos los grafos $G$ y $H$ , $$\gamma(G \square H) \ge \min\{i(G)\gamma(H), i(H)\gamma(G)\}$$

donde $\square$ es el producto cartesiano de los gráficos y $i(G)$ es el número de dominación independiente.

Para los cuadrados cartesianos es $$\gamma(G \square G) \ge \gamma(G) i(G)$$

Según sage y mi cuadrado de verificación del gráfico en 7 vértices $[0 \ldots 6]$ con bordes $$[(0, 4), (0, 5), (0, 6), (1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6)]$$ aparece un contraejemplo a la conjetura 9.6 (nótese que el vértice 3 está desconectado).

Cálculo:

sage: G=Graph(':Fo@I@I@J') #from sparse6
sage: Gs=G.cartesian_product(G)
sage: (Gs.dominating_set(value_only=True),G.dominating_set(value_only=True),G.dominating_set(value_only=True,independent=True) )
(11, 3, 4)

Verificación:

Dado que el pedido es sólo $7$ , $\gamma(G)=3$ y $i(G)=4$ se verificaron enumerando todos los subconjuntos de los vértices. Para $\gamma(G \square G)=11$ el conjunto dominante devuelto por sage fue verificado y es un límite superior para el valor correcto.

Es posible que haya entendido mal la conjetura.

¿Es el gráfico anterior un contraejemplo de la conjetura 9.6?

Añadir vértices desconectados a $G$ da más contraejemplos.

Answer 1

Para resumir un poco:

• $\gamma(G)$ se define como el habitual número de dominio de un gráfico $G$
• $i(G)$ se define como la menor cardinalidad de un conjunto dominante que también es un conjunto independiente

Su gráfico $C$ es la unión disjunta de $K_{3,3}$ y $K_1.$

Claramente $\gamma(C) = 3$ y $i(C) = 4.$ Para los gráficos disjuntos $G,H$ tenemos $$(G \cup H) \square (G \cup H) = (G \square G) \cup (G \square H) \cup (H \square G) \cup (H \square H)$$

que da para $C = K_{3,3} \cup K_1$

$$ C \square C = K_{3,3} \square K_{3,3} \cup K_{3,3} \cup K_{3,3} \cup K_1.$$

Y así $$\gamma(C \square C) = \gamma(K_{3,3} \square K_{3,3}) + 2\gamma(K_{3,3})+\gamma(K_1) = 11.$$

Esto implicaría, en efecto, que $\gamma(C \square C) = 11 < \gamma(C)i(C) = 12.$ Haciendo que la conjetura sea falsa para los grafos desconectados.

Editar . En este papel los autores construyen una familia infinita de grafos que son un contraejemplo a la afirmación de la conjetura 9.6. La familia de grafos construida está desconectada, pero observan que puede hacerse conectada.

Answer 2

Ya que los comentaristas preguntaron por un contraejemplo conectado, aquí está el ejemplo de contador conectado del papel menciona Jernej.

p. 2. A $k$ -La estrella de la hoja es un vértice central con $k$ vértices conectados a él. A $2k$ -hoja-estrella-dos es un gráfico de dos $k$ -Estrellas de hojas con sus vértices centrales conectados por una arista. Definir $G_k$ como la unión disjunta de $2k^2$ -hoja-dos estrellas y $k$ $K_2$ s. $\gamma(G_k)=k+2$ y $i(G_k)=k^2+k+1$ .

El contraejemplo desconectado es $F = G_k \square G_k$ con un conjunto dominante dado $\gamma(F) \le 12k^2+8k+4$ .

Para hacer un contraejemplo conectado $G_k'$ , añade el vértice raíz $r$ a $G_k$ , conéctalo a un centro de las dos estrellas y un vértice de cada $K_2$ .

$\gamma(G_k' \square G_k') \le 16k^2+12k+9$ .

Debido a las constantes el contraejemplo desconectado más pequeño garantizado por la construcción está en $266$ vértices.