2
$\begingroup$

I just learned about line graphs $L(G)$ such that all vertices $v$ in $L(G)$ represent edges in $G$.

Is there a way to inverse this process and for any graph $G$ find $G'$ such that $G$ represents the line graph $L(G)$ of $G'$?

The potential usage of this would be that you could find G' and test it for Eulerianism and then therefore have a algorithm for Hamiltonian cycles. Because of that I assume this must not be possible. If so I would be interested in why it isn't possible?

$\endgroup$
2
$\begingroup$

The simple reason is that not every graph is a line graph, so this inverse won't always exist. For example, the star graph with $4$ vertices (that is, the graph with vertex set $u,v_1,v_2,v_3$ and edges $uv_1,uv_2,uv_3$) is not a line graph.

To see this, suppose that it is the line graph of some other graph $G'$, and use $a,b,c,\ldots$ for vertices of $G'$. $u$ must represent some edge $ab$ say. Then $v_1$ is adjacent to $u$ in the line graph, so represents an edge with a common vertex, say $bc$.

Now $v_2$ has to represent an edge with a vertex in common with $ab$ but not with $bc$. So it represents an edge of the form $ad$. But $v_3$ now has to represent an edge with a vertex in common with $ab$ but not with either $bc$ or $ad$, which is impossible.

$\endgroup$
1
$\begingroup$

In Doug West's Introduction to Graph Theory (2nd Edition), several characterizations (I believe three) of line graphs are given in Section 7.1. There is an intuitive characterization (intuitive after some thought, of course) involving cliques ($G$ is a Line graph of some graph $H$ $\iff$ $G$ can be decomposed into complete subgraphs [cliques] with each vertex of $G$ appearing in at most two said subgraphs.)

Another characterization gives a list of $9$ forbidden induced subgraphs, one of which is $K_{1,3}$ as demonstrated in Especially Lime's answer.

If you don't have access to West's text, you can take a look at the Characterization section of the Wikipedia entry.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.