¿Tiene todo grafo conexo G un árbol de expansión T con el mismo número de dominación?

Question

Sea $G$ sea un grafo simple. Árbol de expansión de un grafo conexo $G$ es un subgrafo acíclico conexo $T$ de $G$ tal que $V_T = V_G$ .

Un conjunto dominante de $G$ es un subconjunto $W$ de $V_G$ tal que cada vértice de $V_G\setminus W$ es adyacente a algún vértice de $W$ . El número de dominación de $G$ , $\gamma(G)$ es el mínimo en las cardinalidades de los conjuntos dominantes de $G$ .

Evidentemente, para cualquier subgrafo de tramo $H$ de $G$ el número de dominación de $H$ está limitado por el número de dominación de $G$ es decir $\gamma(G) \le \gamma(H)$ . En particular, para cada árbol de expansión $T$ de un grafo conexo $G$ , $\gamma(T) \ge \gamma(G)$ .

¿Todo grafo conexo $G$ tienen un árbol de expansión $T$ tal que $\gamma(G)=\gamma(T)$ ?

Answer 1

Sí, y lo que es más, para cualquier conjunto dominante $W$ de $G$ existe un árbol de expansión $T$ para lo cual $W$ también es un conjunto dominante.

Empieza a elegir $T$ recorriendo todos los vértices $v \notin W$ y añadiendo una arista desde $v$ a algún vértice $w \in W \cap N(v)$ . Esto nos da un bosque de estrellas en el que $W$ es un conjunto dominante. Se puede ampliar a un árbol de expansión como se quiera.

Answer 2

Supongamos que $G$ es un gráfico y $X$ es un conjunto tal que cada vértice está en $X$ o adyacente a un vértice en $X$ .

Demostramos que existe un árbol de expansión $T$ de $G$ tal que cada vértice está en $X$ o adyacente a un vértice en $X$ . Para cada vértice $v$ no en $X$ añadimos exactamente una arista desde $v$ a $X$ que se encuentra en $G$ . Después de hacer esto el grafo no tiene ciclos, porque es bipartito, y todos los vértices en $G\setminus X$ tener un título $1$ . Podemos convertir este grafo en un árbol añadiendo aristas en $G$ .