Line graph

2020 Mathematics Subject Classification: Primary: 05C76 [MSN][ZBL]

of a graph $G$

The (unoriented) graph $L(G)$ having a vertex set in one-to-one correspondence with the edge set of $G$, and vertices adjacent in $L(G)$ if the corresponding edges in $G$ have exactly one vertex in common.

The spectra of line graphs have been investigated. Let $G$ have vertices $\{v_1,\ldots,v_n\}$ and edges $e_1,\ldots,e_p$, and let $M$ be the $n \times p$ incidence matrix of $G$, so that $M_{ij} = 1$ if $v_i$ is incident with edge $j$ and otherwise zero. The adjacency matrix $A_L$ of $L(G)$ satisfies $$M^\top M = A_L + 2 I_p$$ where $I_p$ is an identity matrix. It follows that all eigenvalues of $A_L$ are $\ge -2$.

References

• Biggs, Norman Algebraic graph theory 2nd ed. Cambridge University Press (1994) ISBN 0-521-45897-8 Zbl 0797.05032
• Cvetković, Dragoš; Rowlinson, Peter; Simić, Slobodan Spectral generalizations of line graphs. On graphs with least eigenvalue $−2$ London Mathematical Society Lecture Note Series 314 Cambridge University Press(2004) ISBN 0-521-83663-8 Zbl 1061.05057