$\alpha^{'}(G)\geq\frac{n}{1+\Delta(G)}$

Question

Que $G$ ser un gráfico conectado del orden $n$ y $\alpha^{'}(G)$ el borde independencia número (o número correspondiente). ¿Me puede ayudar a demostrar la desigualdad $\alpha^{'}(G)\geq\frac{n}{1+\Delta(G)}$ $\Delta(G)$ ¿Dónde está el grado del vértice máximo?

Answer 1

La respuesta de Adam Lowrance demuestra los siguientes dos teoremas:

Árbol Teorema. Si $G$ es un árbol con $n$ vértices, $n\ge2,$ $$\alpha'(G)\ge\frac n{\Delta(G)+1}.$$

General Teorema. Si $G$ ser un grafo conexo con $n$ vértices, $n\ge2,$ $$\alpha'(G)\ge\frac n{\Delta(G)+1}.$$

He aquí una breve prueba de que el Árbol Teorema. Deje $e(G)=|E(G)|$ ser el tamaño de $G,$ y deje $\chi'(G)$ ser el borde cromática número de $G.$ Si $G$ es un árbol, entonces tenemos $e(G)=n-1\ge\Delta(G)$ $\chi'(G)=\Delta(G),$ dónde $$\alpha'(G)\ge\frac{e(G)}{\chi'(G)}=\frac{n-1}{\Delta(G)}\ge\frac n{\Delta(G)+1}.$$

Aquí está un breve prueba del Teorema General el uso de Vizing del teorema. Sin pérdida de generalidad, podemos suponer que la $G$ es un simple gráfico; por otra parte, podemos suponer que la $G$ no es un árbol. Por Vizing del teorema, $\chi'(G)\le\Delta(G)+1.$ por lo Tanto, desde el $G$ no es un árbol, $e(G)\ge n$ y $$\alpha'(G)\ge\frac{e(G)}{\chi'(G)}\ge\frac n{\Delta(G)+1}.$$

Alternativamente, (sin Vizing del teorema), vamos a $T$ ser un árbol de expansión en $G;$ $$\alpha'(G)\ge\alpha'(T)\ge\frac n{\Delta(T)+1}\ge\frac n{\Delta(G)+1}.$$

Answer 2

Si $G$ es un solo vértice, a continuación,$\alpha'(G) = 0$$\frac{n}{1+\Delta(G)}=1$. Este es un contraejemplo a su desigualdad, pero vamos a ignorarlo y demostrar la declaración para el caso de que $G$ contiene al menos uno de los bordes.

La estrategia es demostrar la declaración a través de la inducción en el número de aristas. El caso base de la inducción será al $G$ es un árbol. La prueba de que he llegado con los árboles utiliza Berge del Lema, y así comenzamos por establecer y afirmar que la lema.

Deje $G=(V,E)$ ser conectado a un simple gráfico con $n$ vértices. Una coincidencia de $M$ es una colección de los bordes, de tal manera que ningún vértice de $G$ es incidente a más de uno de los bordes en $M$. Un vértice que es incidente a un borde en $M$ dijo estar cubierto por $M$. Un aumento de camino de $M$ es un camino en el $G$ de manera tal que el inicio y final de los vértices no están cubiertos por $M$.

Berge del Lexema. Una coincidencia de $M$ $G$ contiene el mayor número posible de los bordes (es decir, $\alpha'(G)$ bordes) si y sólo si la coincidencia de $M$ no tiene ningún aumento de rutas.

Árbol Teorema. Deje $G$ ser un árbol con $n$ vértices y al menos uno de los bordes. Entonces $$\alpha'(G) \geq \frac{n}{1+\Delta(G)}.$$

Prueba. Procedemos por inducción. Nuestra base de casos son al $G$ es un árbol que contiene la ausencia de caminos de longitud 3 o mayor. En estos casos, $G$ es una estrella gráfico (donde estoy considerando la posibilidad de un camino de longitud 1 o 2 como una estrella). Para una estrella gráfico, tenemos $\alpha'(G)=1$$\Delta(G) = n-1$. Así $$\alpha'(G) = 1 = \frac{n}{n}=\frac{n}{1+\Delta(G)}.$$

Deje $G$ ser un árbol que contiene un camino de longitud 3 o más. Deje $M$ ser una coincidencia de $G$ que contiene el mayor número posible de los bordes. Por lo tanto $|M|=\alpha'(G)$. Deje $P$ ser un camino de $G$ de la longitud de por lo menos 3 que empieza y termina en las hojas de $G$. Por Berge del Lexema, ya $M$ es de un máximo de coincidencia, al menos una de las aristas incidentes a los extremos de $P$ debe ser en $M$ (de lo contrario $P$ es un aumento de camino de $M$). Debido a $M$ es una coincidencia, no hay dos consecutivos bordes de $P$$M$. Por lo tanto, no es una ventaja $e$ $P$ no incidente a una hoja de $G$ tal que $e\notin M$.

La eliminación de $e$ $G$ se obtiene el gráfico de $G-e$ que es la desunión de la unión de dos árboles de $G_1$$G_2$. Desde $e$ no es incidente a una hoja en $G$, ambos árboles $G_1$ $G_2$ contienen bordes. Supongamos que $G_1$ $n_1$ vértices, y $G_2$ $n_2$ vértices. Por la hipótesis inductiva, tenemos que $$\alpha'(G_1) \geq \frac{n_1}{1+\Delta(G_1)} ~~ \text{and} ~~ \alpha'(G_2)\geq \frac{n_2}{1+\Delta(G_2)}.$$

El número total de vértices en $G-e$ aún $n$, y por lo $n_1+n_2=n$. También, el máximo grado de cada vértice en $G-e$ satisface $$\Delta(G) -1 \leq \Delta(G-e) \leq \Delta(G).$$ Sin pérdida de generalidad, supongamos que $\Delta(G_1)\leq\Delta(G_2)$. Desde $\Delta(G-e) = \max\{\Delta(G_1),\Delta(G_2)\}$, se deduce que $$\Delta(G)-1 \leq \Delta(G_2) \leq \Delta(G).$$

Deje $E_1$ $E_2$ ser el borde conjuntos de $G_1$ $G_2$ respectivamente, y definir $M_1=M\cap E_1$$M_2=M\cap E_2$. Desde $e\notin M$, se deduce que el $|M_1| + |M_2|=|M|=\alpha'(G)$. También, $\alpha'(G_1)=|M_1|$ $\alpha'(G_2)=|M_2|$ porque de lo contrario podríamos construir una coincidencia en $G$ con más de $|M|=\alpha'(G)$ bordes. Por lo tanto,$\alpha'(G) = \alpha'(G_1) + \alpha'(G_2)$.

Así tenemos \begin{align*} \alpha'(G) = & \; \alpha'(G_1) + \alpha'(G_2)\\ \geq & \; \frac{n_1}{1+\Delta(G_1)} + \frac{n_2}{1+\Delta(G_2)}\\ \geq & \; \frac{n_1}{1+\Delta(G_2)} + \frac{n_2}{1+\Delta(G_2)}\\ = &\; \frac{n}{1+\Delta(G_2)}\\ \geq & \; \frac{n}{1+\Delta(G)}. \end{align*} $$\tag*{$\blacksquare$}$$

Podemos usar el Árbol Teorema como el caso base para nuestros más resultado general.

General Teorema. Deje $G$ ser un grafo conexo con $n$ vértices y al menos uno de los bordes. Entonces $$\alpha'(G) \geq \frac{n}{1+\Delta(G)}.$$

Prueba. Si $G$ es un árbol, luego se realiza por el Árbol Teorema. Así que supongo que $G$ no es un árbol, y deje $M$ ser coincidente con $|M|=\alpha'(G)$. Desde $G$ está conectado y no en un árbol, $G$ contiene un ciclo como un subgrafo. Hay una ventaja $e$ en el ciclo tal que $e\notin M$. Desde $e$ está contenida en un ciclo de la supresión $G-e$ $e$ $G$ permanece conectado.

Desde $M$ es también una coincidencia en $G-e$,$\alpha'(G)= \alpha'(G-e)$. La eliminación de $e$ $G$ puede reducir el grado máximo en uno, y por lo tanto $$\Delta(G) - 1 \leq \Delta(G-e) \leq \Delta(G).$$ Desde $G-e$ también ha $n$ vértices, el inductivo hipótesis de rendimientos $$\alpha'(G-e) \geq \frac{n}{1+\Delta(G-e)}.$$ Por lo tanto $$\alpha'(G) = \alpha'(G-e) \geq \frac{n}{1+\Delta(G-e)} \geq \frac{n}{1+\Delta(G)}.$$ $$\tag*{$\blacksquare$}$$