El número de dominar conjuntos de un bipartito gráfica no es exactamente divisible por $2$

Question

aquí es un lindo problema que he creado desde otro lindo problema. Demostrar que el número de dominar series de un gráfico bipartito nunca es exactamente divisible por $2$.

Dominantes en su conjunto de un grafo es un conjunto de vértices $D$ de manera tal que cada vértice no en $D$ es adyacente a al menos un vértice en $D$

Saludos.

Answer 1

Esto es realmente cierto para todos los gráficos de $G$, y puede ser demostrado mediante la consideración de la Dominación Polinomio de un gráfico; $D(G,x) := \sum_{k=0}^{|V(G)|} d_k(G) x^k$ donde $d_k(G)$ es el número de dominar conjuntos de cardinalidad $k$$G$.

El problema es, pues, mostrar que $D(G,1) \equiv 1 \mod 2$. Hemos demostrado como un corolario de otro resultado en el Subconjunto de la Suma de las Representaciones de la Dominación de los Polinomios. (Gráficos Combinat. 30 (2014), no. 3, 647-660.)

También puede ser demostrado por inducción el uso de este recurrencia de relaciones de Recurrencia y la división de las fórmulas para la dominación del polinomio: (Electrón. J. Combinat. 19 (2012), no. 3, de Papel 47)

$$D(G, x) = xD(G/u, x) + D(G − u, x) + xD(G − N[u], x) − (1 + x)p_u(G, x)$$

Cuando se sustituye $x=1$ en esta se puede ver que el último término es aún y así, hay 3 términos pertenecientes a los más pequeños gráficos que son necesariamente impar por la hipótesis de inducción; 3 números impares añade un número impar.

Las primeras pruebas que hemos encontrado de este resultado fueron publicados por Andries E. Brouwer: El número de dominar conjuntos de un número finito de gráfico es impar.