Return to Answer

math italics to text italics (strange mathjax italic conventions!)

Source Link

edit approved Jan 18, 2017 at 15:01

2.5k
2
20
24

As I understand your question, you are starting with a regular graph of degree $4$ and adding a single edge, so that the graph is no longer regular and no longer a Cayley graph. In that case, if $n=5$, your graph on vertex set $\{0,1,2,3,4\}$ has 11 edges $01, 02, 12, 13, 23, 24, 34,30, 40,41$ and $03$ and the adjacency matrix you give is incorrect.

The regular graph (as Pat Devlin says) has real eigenvalues which are sums of roots of unity. (They are all of the form $2\cos(2c\pi/p)+2\cos(4c\pi/p)$ for integers $c$, $0 \le c \le (p-1)/2$.) It is not immediately clear what the single edge does to the spectrum; yes, it will "perturb" these real numbers into other real numbers, presumably numbers close to the original sums of roots of unity. I think a question about the perturbation of eigenvalues by adding $just$ $one$ edgejust one edge is a good one.

As I understand your question, you are starting with a regular graph of degree $4$ and adding a single edge, so that the graph is no longer regular and no longer a Cayley graph. In that case, if $n=5$, your graph on vertex set $\{0,1,2,3,4\}$ has 11 edges $01, 02, 12, 13, 23, 24, 34,30, 40,41$ and $03$ and the adjacency matrix you give is incorrect.

The regular graph (as Pat Devlin says) has real eigenvalues which are sums of roots of unity. (They are all of the form $2\cos(2c\pi/p)+2\cos(4c\pi/p)$ for integers $c$, $0 \le c \le (p-1)/2$.) It is not immediately clear what the single edge does to the spectrum; yes, it will "perturb" these real numbers into other real numbers, presumably numbers close to the original sums of roots of unity. I think a question about the perturbation of eigenvalues by adding $just$ $one$ edge is a good one.

As I understand your question, you are starting with a regular graph of degree $4$ and adding a single edge, so that the graph is no longer regular and no longer a Cayley graph. In that case, if $n=5$, your graph on vertex set $\{0,1,2,3,4\}$ has 11 edges $01, 02, 12, 13, 23, 24, 34,30, 40,41$ and $03$ and the adjacency matrix you give is incorrect.

The regular graph (as Pat Devlin says) has real eigenvalues which are sums of roots of unity. (They are all of the form $2\cos(2c\pi/p)+2\cos(4c\pi/p)$ for integers $c$, $0 \le c \le (p-1)/2$.) It is not immediately clear what the single edge does to the spectrum; yes, it will "perturb" these real numbers into other real numbers, presumably numbers close to the original sums of roots of unity. I think a question about the perturbation of eigenvalues by adding just one edge is a good one.

Source Link

created Nov 19, 2016 at 13:16

1k
1
9
15

As I understand your question, you are starting with a regular graph of degree $4$ and adding a single edge, so that the graph is no longer regular and no longer a Cayley graph. In that case, if $n=5$, your graph on vertex set $\{0,1,2,3,4\}$ has 11 edges $01, 02, 12, 13, 23, 24, 34,30, 40,41$ and $03$ and the adjacency matrix you give is incorrect.

The regular graph (as Pat Devlin says) has real eigenvalues which are sums of roots of unity. (They are all of the form $2\cos(2c\pi/p)+2\cos(4c\pi/p)$ for integers $c$, $0 \le c \le (p-1)/2$.) It is not immediately clear what the single edge does to the spectrum; yes, it will "perturb" these real numbers into other real numbers, presumably numbers close to the original sums of roots of unity. I think a question about the perturbation of eigenvalues by adding $just$ $one$ edge is a good one.