I am quite sure I have seen somewhere the connection between the characteristic polynomial of a (finite undirected) graph and its dual. I am not able to find it currently. Could you please refer me to the result?

(eigenvalues would be enough)

By dual, I mean the graph where edges become vertices and adjacent if they intersect in a vertex. By characteristic polynomial I mean that of the adjacency matrix.

  • $\begingroup$ I removed my answer since now the question is more specific and needs a new answer. $\endgroup$
    – Shahrooz
    Dec 26, 2019 at 21:59
  • $\begingroup$ The term you are looking for is not "dual graph" (which is usually a term reserved for planar graphs) but "line graph": en.wikipedia.org/wiki/Line_graph $\endgroup$ Dec 26, 2019 at 22:35
  • 1
    $\begingroup$ For a formula for the adjacency matrix eigenvalues of a line graph in terms of the signless Laplacian eigenvalues of the original graph, see section 1.4.5 of homepages.cwi.nl/~aeb/math/ipm/ipm.pdf. $\endgroup$ Dec 26, 2019 at 22:38
  • $\begingroup$ @sam thanks. You may post this as a answer. $\endgroup$ Dec 26, 2019 at 23:36

1 Answer 1


The term for the graph construction you are talking about is "line graph" (see the Wikipedia article). The eigenvalues of the adjacency matrix of the line graph $L(\Gamma)$ are closely related to the signless Laplacian eigenvalues of the original graph $\Gamma$, as explained for instance in section 1.4.5 of these notes (see also Chris Godsil and Gordon Royle's textbook on algebraic graph theory). An important spectral feature of line graphs is that their (adjacency matrix) eigenvalues are at least $-2$.


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.