Árboles cuyo complemento también es un árbol

Question

Estoy buscando esos gráficos $G$ donde $G$ es un árbol y su complemento también es un árbol. Se me ocurrió un gráfico de este tipo $P_4$. ¿Hay algún otro también? No estoy encontrando ningún otro ejemplo. gracias

Answer 1

La que encontraste es única, excepto por el grafo en un vértice.

Considera los siguientes dos hechos:

• Un árbol en $n$ vértices tiene $n-1$ aristas,

• Para un conjunto de $n$ vértices, hay $\binom{n}{2}$ pares (no ordenados), así que el complemento de algún grafo con $m$ aristas tiene $\binom{n}{2} - m$ aristas.

Por lo tanto, si tienes un árbol en $n$ vértices, para que su complemento también sea un árbol, necesitas $\binom{n}{2} - (n-1) = (n-1)$ aristas, lo que da $n(n-1) = 4(n-1)$. Esto puede suceder si $n = 1$ (el grafo de un vértice es su propio complemento, y puede ser llamado un árbol), o si $n = 4$.

Ahora podemos probar exhaustivamente todos los árboles posibles en $4$ vértices (digamos $A, B, C, D$). Solo hay dos de ellos, hasta isomorfismo: el camino A—B—C—D (cuyo complemento es de hecho un árbol), o el árbol donde $A$ está conectado a cada uno de los otros tres, cuyo complemento es un triángulo y no un árbol.

Answer 2

El gráfico en un nodo es otro ejemplo (trivial) más. Vemos que ningún otro gráfico en dos, tres o cuatro nodos cumple la condición.

---

Para evitar $3$-ciclos en el complemento, cada vértice necesita estar conectado con todos los demás excepto posiblemente uno. Si un árbol $T$ tiene $n$ nodos, esto significa $n-2$ nodos conectados.

Entonces elige un vértice arbitrario $v$ en un árbol $T$ con al menos cinco nodos; está conectado con al menos otros tres vértices $w_1, w_2, w_3$. Pero ahora observa el trío $w_1, w_2, w_3$. Al menos uno de los posibles ejes necesita estar ocupado, de lo contrario habrá un ciclo en el complemento $T^c$ de $T$. Sin embargo, cualquier borde de este tipo crearía un ciclo en $T$. Por lo tanto, $T$ no cumple con la condición.

En conclusión, solo pueden existir tales árboles con $4$ nodos o menos. Hemos enumerado esos, y hemos terminado.

Answer 3

Aquí hay una prueba alternativa. Si $n=1$ ya hemos terminado, de lo contrario $n \geq 2.

Cualquier árbol con al menos dos vértices tiene al menos dos hojas. Entonces el complemento tiene al menos dos vértices de grado $n-2$.

Dado que el complemento también es un árbol, tiene al menos dos vértices de grado $n-2$ y al menos $2$ hojas. Entonces, la suma de esos cuatro grados es

$$2(n-2)+2=2(n-1)$$

Pero según el Lema de Handshaking, la suma de todos los grados es $2(n-1)$. Por lo tanto, (dado que el gráfico está conectado) no puede haber ningún otro vértice en el árbol.

Esto muestra que $n=4$, y el árbol debe tener dos vértices de grado $1$ y dos vértices de grado $4-2=2$. Es fácil argumentar que este árbol es $P_4$.