# Eigenvalues of the distance-k graph of a graph

Let $G$ be a (finite, simple, connected) graph. Define the distance-$k$ graph $G_k$ to be the graph with the same vertex set and $x\sim y$ iff $d(x,y)=k$. A graph is integral if all of the eigenvalues of its adjacency matrix are integers.

I have been looking at regular integral graphs. I noticed that when I constructed the distance-2 graphs of these graphs, they were also regular and integral. The regularity part makes sense to me, but I don't have any intuition or understanding of why the integrality might be preserved under this operation.

I haven't been able to find too much about distance-$k$ graphs online other than at http://mathworld.wolfram.com/Distancek-Graph.html. Do you know of any results relating the spectrum of $G_2$ (or of $G_k$) to the spectrum of $G$? General facts about $G_k$ graphs would also be of interest to me.

Thanks.

Let me share some relevant stuff.

One can see that strongly regular graphs with parameters $(v,k, \lambda, \mu)$ for which $2k+(v-1)(\lambda - \mu) \ne 0$ are integral and the respective distance graphs are integral as well.

To see this observe that given the adjacency matrix $A$ of a strongly regular graph $G$ with parameters $(v,k, \lambda, \mu)$ the adjacency matrix of $G_2$ is given by $$\frac{1}{\mu}(A^2 - kI - \lambda A).$$ The eigenvalues of $G$ are $k, \frac{1}{2}( (\lambda - \mu) \pm \sqrt{ (\lambda - \mu)^2 +4(k - \mu)})$ and given the relation $$(v-k-1) \mu = k(k - \lambda -1)$$ that is satisfied for strongly regular graphs one can deduce that $G_2$ is always integral. Since strongly regular graphs have diameter 2 we are done.

For general regular graphs your observation does not hold as can be witnessed by the following figure depicting a $4$-regular graph its distance graph ($k= 2$) and the respective spectrum.

Edit. The respective edges of the graph are $[(0, 4), (0, 6), (0, 7), (0, 8), (1, 5), (1, 6), (1, 7), (1, 11), (2, 6), (2, 8), (2, 10), (2, 11), (3, 7), (3, 8), (3, 9), (3, 11), (4, 8), (4, 9), (4, 10), (5, 9), (5, 10), (5, 11), (6, 9), (7, 10)]$ and $[(0, 1), (0, 2), (0, 3), (0, 9), (0, 10), (1, 2), (1, 3), (1, 9), (1, 10), (2, 3), (2, 4), (2, 5), (2, 7), (2, 9), (3, 4), (3, 5), (3, 6), (3, 10), (4, 5), (4, 6), (4, 7), (5, 6), (5, 7), (6, 7), (6, 8), (6, 10), (6, 11), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (8, 11), (9, 10), (9, 11), (10, 11)]$

• I'm trying to build and analyze your first graph, but some of the vertices look like they are degree five (such as the seventh and tenth vertices from the top) and I can't quite figure out which edges are supposed to be going where. Is there a way that you can redraw it for me? Thanks for always taking the time to answer my questions, by the way. – jamisans May 12 '14 at 5:08
• @jamisans I've edited the post and added the edges of the respective graphs. BTW there are many graphs with this property from what I can see with a computer search – Jernej May 12 '14 at 7:12
• I appreciate you clearing that up and for finding counterexamples. I'm curious now if the graphs I was looking at were exceptional in some way, or if there are additional hypotheses that can be added to make the conclusion true. – jamisans May 12 '14 at 17:02
• @jamisans First thing to look is if they were strongly-regular in which case the property holds (as described above) Can you perhaps post your graphs somewhere? – Jernej May 12 '14 at 17:11
• I don't think they're strongly regular since they've all had more than 3 eigenvalues so far. A lot (but not all) of the graphs I've been looking at have been the graphs described here: mathoverflow.net/questions/159022/…. Here's an example of one of the graphs: i.imgur.com/KYmAMVM.png. And here's its distance-2 graph: i.imgur.com/PhBiXLi.png. – jamisans May 14 '14 at 18:20