L(G) es isomorfo a G si G es un ciclo

Question

Lo contrario es bastante obvio. Si G es un ciclo, entonces es isomorfo a su gráfico lineal. ¿Cómo demostrar que si L(G) es isomorfo a G, entonces G es un ciclo...?

P.D. - Supongamos que G está conectado

Answer 1

Un vértice de $G$ de grado $d_i$ contribuye $\binom{d_i}2$ bordes a $L(G)$ . Entonces con $n$ que denota el número común de vértices y aristas de $G$ y $L(G)$ ,

$$ \sum_id_i=2n\;, $$

$$ \sum_i\frac{d_i(d_i-1)}2=n\;, $$

así que

$$ \sum_id_i^2=4n $$

y por lo tanto

\begin {align} \operatorname {Var}(d)&=E[d^2]-E[d]^2 \\ &= \frac { \sum_id_i ^2}n- \left ( \frac { \sum_id_i }n \right )^2 \\ &=4-4 \\ &=0\;. \end {align}

Así, todos los vértices de ambos gráficos tienen el mismo grado $2$ , lo que sólo ocurre en una unión de grafos de ciclos.

Answer 2

Dejemos que $G$ sea un grafo conexo en $n$ vértices y $m$ bordes y suponga $G$ es isomorfo a su gráfico lineal $L(G)$ . Entonces, $m=n$ y así $G$ es un gráfico conectado que tiene $n$ bordes. Esto implica $G$ es de la forma $T+e$ , donde $T$ es un árbol y $e$ es una arista que no está en $T$ . Si $G=T+e$ es el $n$ -Gráfico del ciclo, entonces hemos terminado.

Supongamos que $T+e$ no es un ciclo. Entonces, $T+e$ tiene un vértice de grado 3 o más. Tres de las aristas incidentes a este vértice en $G$ forman un ciclo de longitud 3 en $L(G)$ . Además, el ciclo único en $G$ obtenido mediante la adición de la arista $e$ al árbol $T$ induce un ciclo en $L(G)$ . Por lo tanto, $L(G)$ tiene al menos dos ciclos. Demostramos que $G$ sólo tiene un ciclo y que $L(G)$ tiene dos o más ciclos, lo cual es una contradicción porque $G \cong L(G)$ . Así que este caso es imposible, y $T+e$ debe ser un ciclo.