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.

It is easy to see that if $G$ is $d$-regular graph then $L(G)$ is $(2d-2)$-regular graph. Thus $2d-2$ is eigenvalue of $L(G)$.

Let $G$ be $d$-regular graph. Is there any relation between the eigenvalues of $L(G)$ and those of $G$?


If $G$ is $k$-regular with $n$ vertices and $m=nk/2$ edges, and if $\phi(M,t)$ is the characteristic polynomial of $M$, then by a result due to Sachs, \[ \phi(L(G),t) = (t+2)^{m-n}\phi(G,t+2-k). \] I am lifting this from page 19 of the 2nd edition of Biggs "Algebraic Graph Theory" (where you will find a proof).


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.