Hallar la inversa de los grafos lineales L(G)

Question

Acabo de aprender sobre gráficos lineales $L(G)$ tal que todos los vértices $v$ en $L(G)$ representan aristas en $G$ .

¿Hay alguna manera de invertir este proceso y para cualquier gráfico $G$ encontrar $G'$ tal que $G$ representa el gráfico lineal $L(G)$ de $G'$ ?

El uso potencial de esto sería que podrías encontrar G' y probarlo para Eulerianismo y entonces tener un algoritmo para ciclos Hamiltonianos. Por eso asumo que esto no debe ser posible. Si es así, me interesaría saber por qué no es posible.

Answer 1

La razón es que no todas las gráficas son rectas, por lo que no siempre existe esta inversa. Por ejemplo, el gráfico de estrella con $4$ vértices (es decir, el grafo con el conjunto de vértices $u,v_1,v_2,v_3$ y bordes $uv_1,uv_2,uv_3$ ) no es un gráfico lineal.

Para ver esto, supongamos que es el gráfico lineal de algún otro gráfico $G'$ y utilice $a,b,c,\ldots$ para vértices de $G'$ . $u$ debe representar alguna arista $ab$ digamos. Entonces $v_1$ es adyacente a $u$ en el grafo lineal, por lo que representa una arista con un vértice común, digamos $bc$ .

Ahora $v_2$ tiene que representar una arista con un vértice en común con $ab$ pero no con $bc$ . Por tanto, representa una arista de la forma $ad$ . Pero $v_3$ ahora tiene que representar una arista con un vértice en común con $ab$ pero tampoco con $bc$ o $ad$ lo cual es imposible.

Answer 2

En Introduction to Graph Theory (2ª edición), de Doug West, se dan varias caracterizaciones (creo que tres) de los grafos lineales en la sección 7.1. Hay una caracterización intuitiva (intuitiva después de pensar un poco, por supuesto) que implica camarillas ( $G$ es un gráfico lineal de algún gráfico $H$ $\iff$ $G$ puede descomponerse en subgrafos completos [camarillas] con cada vértice de $G$ que aparecen como máximo en dos de dichos subgrafos).

Otra caracterización ofrece una lista de $9$ subgrafos inducidos prohibidos, uno de los cuales es $K_{1,3}$ como se demuestra en la respuesta de Especially Lime.

Si no tiene acceso al texto de West, puede echar un vistazo a la sección Caracterización de la Entrada de Wikipedia .