Sedentariness in Cayley graphs

Abstract

Let $A$ be the adjacency matrix of a finite graph $\Gamma$. We say that vertex $u$ of $\Gamma$ is sedentary if for some constant $C>0$, $|\exp (itA{)}_{u,u}|\ge C$ for all $t\in \mathbb{R}$. In this paper, we investigate vertex sedentariness in walk-regular graphs with a focus on Cayley graphs and, more generally, vertex-transitive graphs. In particular, we define the necklace polynomial of an integral graph and use this notion to characterize sedentariness in integral walk-regular graphs. As an application, we use basic tools from algebraic number theory to show that an integral Cayley graph on a group of odd order is sedentary and provide a lower bound on its sedentariness. We also give sufficient conditions such that a unitary Cayley graph over a finite ring is sedentary. Furthermore, we characterize the existence of twin vertices in Cayley graphs and vertex-transitive graphs, and completely determine the occurrence of sedentariness, perfect state transfer and pretty good state transfer in vertex-transitive graphs with twins. Finally, we prove that if $\Gamma (G,S)$ is a nonempty, integral, normal Cayley graph, then for any prime $p$ with $\gcd (p,|G|)=1$, there is at least one eigenvalue of $\Gamma (G,S)$ which is not a multiple of $p$. This generalizes a result of Arnadottir and Godsil, which states that an integral normal Cayley graph of odd order possesses an odd eigenvalue.

arXiv comment29 pages, 1 figure