Describir todos los gráficos sin un camino de longitud 3

Question

Tengo un problema con la siguiente tarea.

Describe todos los grafos que no contengan un camino de longitud 3. ¿Podrías ayudarme a resolverlo?

Answer 1

Sin ninguna condición en el grafo (no estás diciendo ninguna), hay infinitas: es el grafo no está completamente conectado, puedes simplemente añadir vértices aislados.

Si está conectado, también hay infinitos, puedes conectar un vértice con todos los que quieras, así que tienes n+1 vértices, uno de ellos de n grado, y el resto de 1 grado, formas una estrella.

Ten en cuenta que tienes que formar el gráfico a partir de partes que sean como mucho, 3 vértices formando una línea, y no puedes conectar más vértices a los vértices exteriores porque tendrás un camino de longitud 3. Así que sólo puedes conectar más vértices al del medio. Ahora bien, puedes conectar ahí, bien un vértice, bien otra parte de tres, haciendo que el vértice del medio sea el mismo que el vértice del medio en el gráfico anterior: esto es equivalente a conectar dos vértices al medio, por lo que lo único que puedes hacer es, a partir de un vértice inicial, conectar más vértices sólo a ese vértice.

La conclusión es que el grafo está formado por componentes desconectados formados por un vértice conectado a k vértices de grado 1, con $k\in\mathbf{N}$

Answer 2

Pista: ¿puedes decir algo sobre los grados de los vértices de tu gráfico? Tal vez quieras dividir primero el gráfico en componentes conectados.

Answer 3

Se buscan los gráficos cuyas componentes conectadas son estrellas . En particular, las estrellas son árboles con un diámetro máximo de 2, y todos los no-árboles simples tienen un diámetro mínimo de 3.

Answer 4

Normalmente se considera el camino de longitud 3:

Llamémoslo $P_3$ . Y estamos buscando gráficos que no tengan un $P_3$ subgrafo.

Cualquier gráfico de este tipo es la unión de componentes conectados con cada componente que no tiene $P_3$ subgrafo.

Trivialmente, todos los grafos conectados en $3$ o menos vértices no tienen $P_3$ subgrafo. ( Nota : esto incluye el triángulo $K_3$ omitido en dos de las respuestas anteriores).

Supongamos ahora que un componente conectado tiene $\geq 4$ vértices.

• Reclamación : Este componente debe ser un árbol. En caso contrario, o bien contiene un subgrafo isomorfo a

  

  que contiene un $P_3$ subgrafo (como el resaltado), o un ciclo $C_k$ para $k \geq 4$ que contienen $P_3$ subgráficos. En cualquier caso, llegamos a una contradicción.

• Reclamación : Hay un único vértice de grado $\geq 2$ .

  En caso contrario, existe un camino entre dos vértices $i$ y $j$ de grado $\geq 2$ que juntos forman un subgrafo que contiene un $P_3$ subgrafo (hay algunos casos que comprobar aquí; omitiré los detalles dolorosos), dando una contradicción.

Por lo tanto, cualquier componente conectado con $4$ o más vértices es una estrella (es decir, $K_{1,k}$ para $k \geq 3$ ).

Por lo tanto, los grafos sin subgrafos son isomorfos a $P_3$ son la unión de los gráficos en $$\{K_1,K_2,K_3\} \cup \{K_{1,k}: k \geq 2\}.$$