2
$\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?

Let $G$ be $d$-regular graph. For $d=2$, $G$ will be cycle graph, in this case it is easy to check that $L(G)=G$, thus $L(L(G))=G$ ($i.e.$ line graph of the line graph gives us the initial graph).

My question is for which $d\geq 3$ we have $L(L(G))=G$?

I think that $L(L(G))=G$ if and only if $d=2$, but I'm not sure how to prove it.

Any idea will be useful!

$\endgroup$
  • 1
    $\begingroup$ +1 for question and answer, I think I can use this result as check for my linear algebra implementation of the mapping $L(G)$... $\endgroup$ – draks ... Apr 5 '16 at 8:46
3
$\begingroup$

The answer is pretty easy!

Proposition:

Let $G$ be $k$-regular graph (that is $d(G)=k$), then $L(L(G))=G$ if and only if $k=2$

proof

-If $k=2$, then $L(L(G))=G$.

-If $L(L(G))=G$, then $$d(L(L(G)))=d(G)=k$$

But we know that $d(L(G))=2k-2\Rightarrow d(L(L(G)))=4k-6$, then $$4k-6=k\Rightarrow k=2$$

$\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.