betaFeedback

WorksMathematics

Sedentariness in Cayley graphs

Abstract

Let AA be the adjacency matrix of a finite graph ΓΓ. We say that vertex uu of ΓΓ is sedentary if for some constant C>0C>0, ∣exp⁡(itA)u,u∣≥C|\exp(itA)_{u,u}|\geq C for all t∈Rt\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 Γ(G,S)Γ(G,S) is a nonempty, integral, normal Cayley graph, then for any prime pp with gcd⁡(p,∣G∣)=1\gcd(p, |G|)=1, there is at least one eigenvalue of Γ(G,S)Γ(G,S) which is not a multiple of pp. This generalizes a result of Arnadottir and Godsil, which states that an integral normal Cayley graph of odd order possesses an odd eigenvalue.

Introduction

Throughout this paper, we let Γ\Gamma be a graph on nn vertices with vertex set V(Γ)V(\Gamma) and adjacency matrix A=A(Γ)A=A(\Gamma). A (continuous) quantum walk on Γ\Gamma is determined by a one-parameter family of complex symmetric n×nn \times n unitary matrices:

U(t)=eitAt∈R.U(t)=e^{\mathrm{i}tA}\quad t\in\mathbb{R}.

We call U(t)U(t) the transition matrix of Γ\Gamma. A quantum walk on Γ\Gamma describes the propagation of quantum states in the spin network modeled by Γ\Gamma. Since U(t)U(t) is unitary for all tt, we have

∑j=1n∣U(t)u,j∣2=1.(1)\sum_{j=1}^{n}|U(t)_{u,j}|^2=1. \tag*{(1)}

So, we may interpret ∣U(t)u,v∣2|U(t)_{u,v}|^2 as the probability that the quantum state assigned at vertex uu is transmitted to vertex vv at time tt. If ∣U(τ)u,v∣=1|U(\tau)_{u,v}|=1 for some time τ>0\tau>0, then we say that perfect state transfer (PST) occurs between uu and vv at time τ\tau. A relaxation of PST is called pretty good state transfer (PGST), which occurs between uu and vv if there is a sequence {τk}\{\tau_k\} such that lim⁡k→∞∣U(τk)u,v∣=1\lim_{k\to\infty}|U(\tau_k)_{u,v}|=1. On the other hand, if there is a constant C>0C>0 such that

inf⁡t>0∣U(t)u,u∣≥C,(2)\inf_{t>0}|U(t)_{u,u}|\ge C, \tag*{(2)}

then we say that vertex uu is CC-sedentary. If CC does not matter, then we simply say sedentary in lieu of CC-sedentary. From (1.1), it follows that PGST and vertex sedentariness are mutually exclusive. That is, a vertex involved in PGST is not sedentary, and a sedentary vertex is not involved in PGST. Further, we say that Γ\Gamma is sedentary if each vertex of Γ\Gamma is sedentary.

For a sedentary vertex uu, define C:=inf⁡t>0∣U(t)u,u∣\mathcal{C}:=\inf_{t>0}|U(t)_{u,u}|. Note that C\mathcal{C} is the largest possible C>0C>0 such that vertex uu is CC-sedentary. It is desirable to obtain the exact value, or a good approximation, of C\mathcal{C} whenever possible, for this allows us to provide a rough upper bound for ∣U(t)u,v∣|U(t)_{u,v}| for all t∈Rt\in\mathbb{R}. Indeed, for two vertices uu and vv in Γ\Gamma, we have ∣U(t)u,u∣2+∣U(t)u,v∣2≤1|U(t)_{u,u}|^2+|U(t)_{u,v}|^2\le1 for all t∈Rt\in\mathbb{R} by (1.1). Thus, if uu is sedentary, then ∣U(t)u,u∣≥C|U(t)_{u,u}|\ge\mathcal{C} for all tt, and so

∣U(t)u,v∣≤1−C2for all t∈R.|U(t)_{u,v}|\le\sqrt{1-\mathcal{C}^2}\quad\text{for all }t\in\mathbb{R}.

In [8], it is shown that the above bound is related to peak state transfer, which is another relaxation of PST first studied in [10].

This paper is organized as follows. Section 2 is allotted to basic definitions and notation relevant to the rest of the paper. In Section 3, we recall known results about sedentariness in twins, and completely characterize PST, PGST and vertex sedentariness in graphs that are wreath products with a complete or empty graph (also known as blow-up graphs in the literature) (Theorem 3.7 and Corollary 3.8). In Section 4, we provide sufficient conditions for sedentariness in walk-regular graphs (Corollary 4.6) and show that a vertex in a walk-regular graph is sedentary if and only if every vertex is (Proposition 4.5). In Section 5, we define the necklace polynomial of an integral graph and use this to characterize sedentariness in integral walk-regular graphs. In particular, we show that an integral walk-regular graph is sedentary if and only if its associated necklace polynomial has no roots on the unit circle (Theorem 5.7). Using tools from basic algebraic number theory, we show that a connected, integral, walk-regular graph is sedentary whenever the multiplicity of each of its eigenvalues, except the valency, is a multiple of some integer greater than one (Theorem 5.12). Moreover, for this family of sedentary graphs, we use the theory of resultants to derive a lower bound on the sedentariness (Theorem 5.18). In § 6, we apply our results to Cayley graphs. In particular, we show that an integral Cayley graph on a group of odd order is sedentary (Theorem 6.3), and derive sufficient conditions such that a UU-unitary Cayley graph is sedentary. Our goal in § 7 is two-fold: we characterize the existence of twins in Cayley graphs and vertex-transitive graphs (Lemmas 7.3, 7.7, and Theorem 7.9), and we use this characterization to completely determine PST, PGST and sedentariness in vertex-transitive graphs with twins (Theorem 7.10 and Corollary 7.11). In § 8, we also investigate whether certain modular properties hold for eigenvalues of integral graphs and Cayley graphs. Finally, we present open questions in § 9.

Preliminaries

Let Γ\Gamma be a graph on nn vertices. Throughout the paper, we refer to the eigenvalues and eigenvectors of A(Γ)A(\Gamma) as the eigenvalues and eigenvectors of Γ\Gamma. We order the eigenvalues of Γ\Gamma in a nonincreasing order λ1≥λ2≥⋯≥λn\lambda_1 \ge\lambda_2 \ge\cdots\ge\lambda_n. The spectrum of Γ\Gamma, denoted spec⁡(Γ)\operatorname{spec}(\Gamma), is the multiset of eigenvalues of A(Γ)A(\Gamma) (counted with multiplicity). For convenience, we also denote by σ(Γ)\sigma(\Gamma) the set of distinct eigenvalues of Γ\Gamma. We sometimes use spec⁡(Γ)\operatorname{spec}(\Gamma) and σ(Γ)\sigma(\Gamma) interchangeably when multiplicities are not relevant. The meaning will be clear from the context. For each λ∈σ(Γ)\lambda\in\sigma(\Gamma), we let EλE_\lambda denote the orthogonal projection matrix associated with the λ\lambda-eigenspace of A(Γ)A(\Gamma). The (eigenvalue) support of vertex uu in Γ\Gamma, denoted Φu(Γ)\Phi_u(\Gamma), is the set

Φu(Γ)={λ∈σ(Γ):(Eλ)u,u≠0}.\Phi_u(\Gamma) = \{\lambda\in\sigma(\Gamma) : (E_\lambda)_{u,u} \ne0\}.

If Γ\Gamma is clear from the context, then we write Φu(Γ)\Phi_u(\Gamma) as Φu\Phi_u. We also remark that λ∈Φu(Γ)\lambda\in\Phi_u(\Gamma) if and only if there is an eigenvector w\mathbf{w} for Γ\Gamma associated with λ\lambda that has a nonzero uuth entry.

We write MTM^T and M∗M^* for the transpose and conjugate transpose of a matrix MM. We let ImI_m, OmO_m, JmJ_m denote the m×mm \times m identity, zero and all-ones matrix. If the context is clear, then we omit the subscripts. We use boldface lowercase letters to denote vectors. We denote the empty, complete, path and cycle on mm vertices by OmO_m, KmK_m, and PmP_m, respectively, and the complete bipartite graph with parts of size rr and ss by Kr,sK_{r,s}. We write Γ1≅Γ2\Gamma_1 \cong\Gamma_2 to denote that Γ1\Gamma_1 and Γ2\Gamma_2 are isomorphic graphs. We also denote the automorphism group of Γ\Gamma by Aut⁡(Γ)\operatorname{Aut}(\Gamma).

Next, we review a few basic graph operations. Let Γ1\Gamma_1 and Γ2\Gamma_2 be two graphs. Let ⊕\oplus and ⊗\otimes denote the direct sum and Kronecker product on matrices. The union of Γ1\Gamma_1 and Γ2\Gamma_2, denoted Γ1⊔Γ2\Gamma_1 \sqcup\Gamma_2, is the graph with vertex set V(Γ1)∪V(Γ2)V(\Gamma_1) \cup V(\Gamma_2) and adjacency matrix A(Γ1)⊕A(Γ2)A(\Gamma_1) \oplus A(\Gamma_2). The direct product, Cartesian product, and wreath product of Γ1\Gamma_1 and Γ2\Gamma_2, denoted Γ1×Γ2\Gamma_1 \times\Gamma_2, Γ1□Γ2\Gamma_1 \square\Gamma_2, and Γ1[Γ2]\Gamma_1[\Gamma_2], are the graphs with vertex set V(Γ1)×V(Γ2)V(\Gamma_1) \times V(\Gamma_2) and adjacency matrices

A(Γ1)⊗A(Γ2),A(Γ1)⊗I+I⊗A(Γ2),andA(Γ1[Γ2])=A(Γ1)⊗J+I⊗A(Γ2),A(\Gamma_1) \otimes A(\Gamma_2), \qquad A(\Gamma_1) \otimes I + I \otimes A(\Gamma_2), \qquad\text{and} \qquad A(\Gamma_1[\Gamma_2]) = A(\Gamma_1) \otimes J + I \otimes A(\Gamma_2),

respectively, where II and JJ are the identity and all-ones square matrices of appropriate sizes. We denote the union, direct product and Cartesian product of kk copies of Γ\Gamma by ⨆kΓ\bigsqcup_k \Gamma, Γ×k\Gamma^{\times k}, and Γ□k\Gamma^{\square k}, respectively. The complement of Γ\Gamma, denoted Γ‾\overline{\Gamma}, is the graph with V(Γ)=V(Γ‾)V(\Gamma) = V(\overline{\Gamma}) and

A(Γ‾)=J−I−A(Γ).A(\overline{\Gamma}) = J - I - A(\Gamma).

From [6], it is known that

spec⁡(Γ1⊔Γ2)=spec⁡(Γ1)∪spec⁡(Γ2),spec⁡(Γ1×Γ2)={λμ:λ∈spec⁡(Γ1), μ∈spec⁡(Γ2)},spec⁡(Γ1□Γ2)={λ+μ:λ∈spec⁡(Γ1), μ∈spec⁡(Γ2)}.(3)\begin{aligned} \operatorname{spec}(\Gamma_1 \sqcup\Gamma_2) &= \operatorname{spec}(\Gamma_1) \cup\operatorname{spec}(\Gamma_2),\\ \operatorname{spec}(\Gamma_1 \times\Gamma_2) &= \{\lambda\mu: \lambda\in\operatorname{spec}(\Gamma_1),\ \mu\in\operatorname{spec}(\Gamma_2)\},\\ \operatorname{spec}(\Gamma_1 \square\Gamma_2) &= \{\lambda+\mu: \lambda\in\operatorname{spec}(\Gamma_1),\ \mu\in\operatorname{spec}(\Gamma_2)\}. \tag*{(3)} \end{aligned}

If we further assume that Γ2\Gamma_2 is regular with valency dd, then

References

  1. [1]R. Akhtar, M. Boggess, T. Jackson-Henderson, I. Jiménez, R. Karpman, A. Kinzel, and D. Pritikin, On the unitary Cayley graph of a finite ring, Electron. J. Comb. 16 (2009), no. 1, R117.DOI
  2. [2]R. Alvir, S. Dever, B. Lovitz, J. Myer, C. Tamon, Y. Xu, and H. Zhan, Perfect state transfer in Laplacian quantum walk, J. Algebr. Comb. 43 (2016), no. 4, 801–826.arxiv.org/abs/1409.5840
  3. [3]A.S. Arnadottir and C. Godsil, A note on eigenvalues of Cayley graphs, Linear Algebra Appl. 721 (2025), 240–249.
  4. [4]M. Bašić, Characterization of quantum circulant networks having perfect state transfer, Quantum Inf. Process. 12 (2013), no. 1, 345–364.DOI
  5. [5]B. Bhattacharjya, H. Monterde, and H. Pal, Quantum walks on blow-up graphs, J. Phys. A: Math. Theor. 57 (2024), no. 33, 335303.arxiv.org/abs/2308.13887
  6. [6]A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Universitext, Springer, New York, 2012.
  7. [7]M. Chudnovsky, M. Cizek, L. Crew, Ján Mináč, T. T. Nguyen, S. Spirkl, and N. D. Tân, On prime Cayley graphs, J. Comb. 17 (2026), no. 2, 223–252.arxiv.org/abs/2401.06062
  8. [8]J. Cooper, H. De Vera, H. Monterde, SA Talebbour, and X. Wang, Quantum walks and graph operations, arXiv preprint arXiv:2610.07673 (2026).arxiv.org/abs/2610.07673
  9. [9]G. Coutinho, Quantum State Transfer in Graphs, Ph.D. thesis, University of Waterloo, 2014.
  10. [10]G. Coutinho, K. Guo, and V. Schmeits, Peak state transfer in continuous quantum walks, arXiv preprint arXiv:2505.11986 (2025).arxiv.org/abs/2505.11986
  11. [11]David A Cox, John B Little, Donal O’Shea, and John Little, Ideals, Varieties, and Algorithms: an introduction to computational algebraic geometry and commutative algebra, vol. 10, Springer, 2007.
  12. [12]Persi Diaconis and Mehrdad Shahshahani, Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete 57 (1981), no. 2, 159–179. MR 626813DOI
  13. [13]C. Godsil, Periodic graphs, Electron. J. Comb. 18 (2011), no. 1, 1–15.
  14. [14]———, Sedentary quantum walks, Linear Algebra Appl. 614 (2021), 356–375.arxiv.org/abs/1710.11192
  15. [15]C. Godsil and P. Spiga, Integral normal Cayley graphs, J. Algebr. Comb. 62 (2025), no. 1, 20.DOI
  16. [16]D. A. Gregory, D. Hershkowitz, and S. J. Kirkland, The spread of the spectrum of a graph, Linear Algebra Appl. 332 (2001), 23–35.DOI
  17. [17]T. Honold, Characterization of finite frobenius rings, Arch. Math. 76 (2001), no. 6, 406–415.DOI
  18. [18]T. Hyde, Cyclotomic factors of necklace polynomials, Acta Arith. 204 (2022), 287–316.arxiv.org/abs/1811.08601
  19. [19]S. Kirkland and H. Monterde, Quantum walks on join graphs, Discrete Math. 349 (2026), no. 3, 114832.arxiv.org/abs/2312.06906
  20. [20]S. Kirkland, H. Monterde, and S. Plosker, Quantum state transfer between twins in weighted graphs, J. Algebr. Comb. 58 (2023), no. 3, 623–649.DOI
  21. [21]W. Klotz and T. Sander, Some properties of unitary Cayley graphs, Electron. J. Comb. 14 (2007), no. 1, R45.DOI
  22. [22]K. Meagher and H. Monterde, Sedentary quantum walks on bipartite and planar graphs, arXiv preprint arXiv:2601.18964 (2026).arxiv.org/abs/2601.18964
  23. [23]N. C. Minh, N. V. H. Minh, D. Nguyen, T. T. Nguyen, N. D. Tan, and D. Tran, Cyclotomic factors of rational necklace functions, arXiv preprint arXiv:2606.02324 (2026).arxiv.org/abs/2606.02324
  24. [24]H. Monterde, Strong cospectrality and twin vertices in weighted graphs, Electron. J. Linear Algebra. 38 (2022), 494–518.DOI
  25. [25]———, Sedentariness in quantum walks, Quantum Inf. Process. 22 (2023), no. 7, Paper No. 273, 27. MR 4612428DOI
  26. [26]———, New results in vertex sedentariness, Discrete Math. 349 (2026), no. 4, 114959.arxiv.org/abs/2401.00362
  27. [27]H. Monterde, H. Pal, and S. Kirkland, Laplacian quantum walks on blow-up graphs, Linear Algebra Appl. (2025).arxiv.org/abs/2504.11585
  28. [28]T. T. Nguyen and N. D. Tân, Integral Cayley graphs over a finite symmetric algebra, Arch. Math. 124 (2025), no. 6, 615–623.arxiv.org/abs/2411.00307
  29. [29]———, Supercharacters of finite abelian groups and applications to spectra of u-unitary Cayley graphs, arXiv preprint arXiv:2508.10348 (2025).arxiv.org/abs/2508.10348
  30. [30]———, On gcd-graphs over finite commutative rings, J. Algebra Appl. (2026).
  31. [31]———, On U-unitary Cayley graphs over finite rings, arXiv preprint arXiv:2603.21239 (2026).
  32. [32]H. Pal, Quantum state transfer on a class of circulant graphs, Linear Multilinear Algebra 69 (2021), no. 13, 2527–2538.
  33. [33]D.S. Passman, Lecture notes in pure and applied mathematics, M. Dekker, 1971.
  34. [34]J.-P. Serre, Linear Representations of Finite Groups, vol. 42, Springer, 1977.DOI
  35. [35]W. So, Integral circulant graphs, Discrete Math. 306 (2006), no. 1, 153–158.DOI

Paper details

vlnc:W_pfuh6xbb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents