Diámetro de un gráfico conectado

Question

Problema

1. Demostrar que si $G$ está conectado y $\text{ diam}(G) \geq 3$ entonces $\overline{G}$ está conectado.
2. Demostrar que si $\text{ diam}(G) \geq 3$ entonces $\text{ diam}(\overline{G}) \leq 3.$
3. Demostrar que si $G$ es regular y $\text{ diam}(G) = 3$ entonces $\text{ diam}(\overline{G}) = 2$ .

Acérquese a

Intenté encontrar relaciones entre los diámetros de $G$ y $\overline{G}$ Pero lo único que se me ocurre es que el efecto de añadir aristas al gráfico reduce el diámetro en la mayoría de los casos, pero no necesariamente.

Cualquier ayuda será muy apreciada.

Answer 1

(1) Que $G$ sea un gráfico conectado. Supongamos que $\bar{G}$ (el complemento de $G$ ) se desconecte. Demostraremos que $G$ tiene $diam(G)\le 2$ . (por lo tanto, probando la afirmación por contra-positiva)

Dejemos que $C_1,C_2,\dots C_n$ sean componentes conectados de $\bar{G}$ . Desde, $\bar{G}$ está desconectado, hay al menos dos componentes conectados. En $G$ ,

1. hay una arista entre dos vértices cualesquiera que pertenecen a diferentes componentes conectados de $\bar{G}$ .
2. Para dos vértices cualesquiera que pertenezcan a un componente conectado de $\bar{G}$ existe un camino que los conecta a través de un vértice perteneciente a un componente de conexión diferente.

Por lo tanto, $diam(G)\le 2$ . El caso de $diam(G)=1$ se produce cuando $\bar{G}$ no tiene ninguna arista.

(2) Que $diam(G)\ge 3$ . Si $G$ está desconectado, entonces $\bar{G}$ está relacionado con $diam(\bar{G})=2$ (de 1). Supongamos que G es conexo y $diam(G)=k\ge 3$ . Sea $v_1$ y $v_{k+1}$ sean dos vertientes de $G$ conectados a través del camino más corto de longitud $k$ . Sea $L_r:=\{v \mid \, \text{ length of the shortest path between } v_1 \text{ and } v \text{ is } r, 1\le r\le k-1\}$ . Desde, $v_{k+1}$ existe, $L_r\ne \emptyset \, ,\, \forall \, 1\le r\le k-1$ .

En $\bar{G}$ ,

1. $v_1$ está conectado a $v_{k+1}$ a través de un borde.
2. $v_1$ está conectado a cualquier elemento de $L_r$ donde $2\le r\le k-1$ a través de un borde.( $v_{k+1}$ está conectado a cualquier elemento de $L_r$ donde $1\le r\le k-2$ a través de un borde)
3. $v_1$ está conectado a cualquier elemento de $L_1$ a través de $v_{k+1}$ . ( $v_{k+1}$ está conectado a cualquier elemento de $L_{k-1}$ a través de $v_{1}$ )
4. Dejemos que $1\le i\le k-1$ y $1\le j\le k-1$ . Si $\mid i-j \mid>1$ Cualquier dos vértices de $L_i$ y $L_j$ son adyacentes. Si $i-j=1$ , dos cualesquiera vértices de $L_i$ y $L_j$ están conectados a través de $v_{L_i} \to v_1 \to v_{L_j}\to v_{k+1}$ donde $v_{L_i}$ y $v_{L_j}$ son dos cualesquiera vértices pertenecientes a $L_i$ y $L_j$ respectivamente.

Esto lo demuestra, $diam(\bar{G})\le 3$

(3) Que $G$ sea un grafo regular con grado de vértice $k$ y $diam(G)=3$ . Utilizando la misma notación que en (2), dejemos que $v_1$ y $v_4$ sean dos vértices tales que el camino más corto entre ellos tiene una longitud $3$ . Desde, $G$ es regular con grado $k$ , ambos $L_1$ y $L_2$ contienen $k$ vértices cada uno. Hay $2k+2$ vértices y $k(k+1)$ bordes. En, $\bar{G}$ un camino desde un vértice en $L_1$ a un vértice en $L_2$ en las líneas de 4 de (2) tiene longitud $3$ . Sea $G'$ sea el gráfico obtenido al eliminar los vértices $v_1$ y $v_4$ de $G$ (por lo tanto, borrando también todas las aristas que inciden en ellas).

Tenga en cuenta que $\bar{G'}$ es un gráfico regular de grado $2k-1-(k-1)=k$ y $2k$ vértices. Supongamos que $diam(\bar{G'})\ge 3$ entonces no podemos dividir los vértices de $\bar{G'}$ en la forma $\{v_1,L_1,\dots,L_m,v_{m+1}\}$ para algunos $m\ge 3$ ya que necesitaríamos al menos $2+\mid L_1\mid +\mid L_{m} \mid=2k+2$ vértices mientras que nosotros sólo tenemos $2k$ vértices. Por lo tanto, demostramos que $diam(\bar{G'})=2$ y por lo tanto $diam(\bar{G})=2$ . ( $diam(\bar{G})=1$ significaría que $G$ no tenía ninguna arista, lo que contradice el hecho de que $diam(G)=3$ )