2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I removed my answer since now the question is more specific and needs a new answer. $\endgroup$ – Shahrooz Janbaz Dec 26 '19 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$ – Sam Hopkins Dec 26 '19 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$ – Sam Hopkins Dec 26 '19 at 22:38
  • $\begingroup$ @sam thanks. You may post this as a answer. $\endgroup$ – user2679290 Dec 26 '19 at 23:36
2
$\begingroup$

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

| cite | improve this answer | |
$\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.