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.

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

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .