3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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. enter image description here

enter image description here

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)]$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – jamisans May 12 '14 at 5:08
  • $\begingroup$ @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 $\endgroup$ – Jernej May 12 '14 at 7:12
  • $\begingroup$ 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. $\endgroup$ – jamisans May 12 '14 at 17:02
  • $\begingroup$ @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? $\endgroup$ – Jernej May 12 '14 at 17:11
  • $\begingroup$ 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. $\endgroup$ – jamisans May 14 '14 at 18:20

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.