1
$\begingroup$

Definition:

Let $G$ be a graph, the line graph of $G$ denoted of $L(G)$ is defined as follows:

-The vertices of $L(G)$ are the edges of $G$

-Two vertices of $L(G)$ are adjacent iff their corresponding edges in $G$ are incident G.

Question?

It is easy to see that if $G$ is $d$-regular graph then $L(G)$ is $(2d-2)$-regular graph. Thus we have $L(L(G))\neq G$. My question is there graph let's say $L^{-1}$, such that $L^{-1}(L(G))=G$?

Any idea will be useful!

$\endgroup$
1
$\begingroup$

Line graphs are not in bijection with graphs, so strictly speaking there is no inverse operation. However, it is still possible to reconstruct the original graphs (there are linear time algorithms), but the construction is not as direct as the line graph construction. So you could add more information when constructing the line graph, and use $L'(G)$ instead of $L(G)$, which gives a coloured graph where each vertex has two colors (encoding the original vertices of $G$), so that you can get an easy definition for $L'^{-1}$ with $L'^{-1}(L(G)) = G$.

$\endgroup$
0
$\begingroup$

Consider the n cycle $c_n$ it's vertices are $0,...n$ there is an edge between $i$ and $i+1$ and an edge between $n$ and $1$. $L(c_n)=c_n$ so $L(L(c_n))=c_n$.

$\endgroup$
  • $\begingroup$ This is particular case, since $d=2$, then $2d-2=2$, and since the graph is connected then the line graph of cycle will be always cycle. If we take any $d$-regular $G$ with $d\geq 3$, then $L(G)\neq G$. $\endgroup$ – M.Badaoui Mar 31 '16 at 19:05

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.