Introduction
Throughout this paper, we let Γ \Gamma Γ be a graph on n n n vertices with vertex set V ( Γ ) V(\Gamma) V ( Γ ) and adjacency matrix A = A ( Γ ) A=A(\Gamma) A = A ( Γ ) . A (continuous) quantum walk on Γ \Gamma Γ is determined by a one-parameter family of complex symmetric n × n n \times n n × n unitary matrices:
U ( t ) = e i t A t ∈ R . U(t)=e^{\mathrm{i}tA}\quad t\in\mathbb{R}. U ( t ) = e i t A t ∈ R .
We call U ( t ) 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) U ( t ) is unitary for all t t t , we have
∑ j = 1 n ∣ U ( t ) u , j ∣ 2 = 1. (1) \sum_{j=1}^{n}|U(t)_{u,j}|^2=1. \tag*{(1)} j = 1 ∑ n ∣ U ( t ) u , j ∣ 2 = 1. (1)
So, we may interpret ∣ U ( t ) u , v ∣ 2 |U(t)_{u,v}|^2 ∣ U ( t ) u , v ∣ 2 as the probability that the quantum state assigned at vertex u u u is transmitted to vertex v v v at time t t t . If ∣ U ( τ ) u , v ∣ = 1 |U(\tau)_{u,v}|=1 ∣ U ( τ ) u , v ∣ = 1 for some time τ > 0 \tau>0 τ > 0 , then we say that perfect state transfer (PST ) occurs between u u u and v v v at time τ \tau τ . A relaxation of PST is called pretty good state transfer (PGST ), which occurs between u u u and v v v if there is a sequence { τ k } \{\tau_k\} { τ k } such that lim k → ∞ ∣ U ( τ k ) u , v ∣ = 1 \lim_{k\to\infty}|U(\tau_k)_{u,v}|=1 lim k → ∞ ∣ U ( τ k ) u , v ∣ = 1 . On the other hand, if there is a constant C > 0 C>0 C > 0 such that
inf t > 0 ∣ U ( t ) u , u ∣ ≥ C , (2) \inf_{t>0}|U(t)_{u,u}|\ge C, \tag*{(2)} t > 0 inf ∣ U ( t ) u , u ∣ ≥ C , (2)
then we say that vertex u u u is C C C -sedentary. If C C C does not matter, then we simply say sedentary in lieu of C C C -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 u u u , define C : = inf t > 0 ∣ U ( t ) u , u ∣ \mathcal{C}:=\inf_{t>0}|U(t)_{u,u}| C := inf t > 0 ∣ U ( t ) u , u ∣ . Note that C \mathcal{C} C is the largest possible C > 0 C>0 C > 0 such that vertex u u u is C C C -sedentary. It is desirable to obtain the exact value, or a good approximation, of C \mathcal{C} C whenever possible, for this allows us to provide a rough upper bound for ∣ U ( t ) u , v ∣ |U(t)_{u,v}| ∣ U ( t ) u , v ∣ for all t ∈ R t\in\mathbb{R} t ∈ R . Indeed, for two vertices u u u and v v v 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 ∣ U ( t ) u , u ∣ 2 + ∣ U ( t ) u , v ∣ 2 ≤ 1 for all t ∈ R t\in\mathbb{R} t ∈ R by (1.1). Thus, if u u u is sedentary, then ∣ U ( t ) u , u ∣ ≥ C |U(t)_{u,u}|\ge\mathcal{C} ∣ U ( t ) u , u ∣ ≥ C for all t t t , and so
∣ U ( t ) u , v ∣ ≤ 1 − C 2 for all t ∈ R . |U(t)_{u,v}|\le\sqrt{1-\mathcal{C}^2}\quad\text{for all }t\in\mathbb{R}. ∣ U ( t ) u , v ∣ ≤ 1 − C 2 for all t ∈ 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 U U U -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 n n n vertices. Throughout the paper, we refer to the eigenvalues and eigenvectors of A ( Γ ) A(\Gamma) A ( Γ ) 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 λ 1 ≥ λ 2 ≥ ⋯ ≥ λ n . The spectrum of Γ \Gamma Γ , denoted spec ( Γ ) \operatorname{spec}(\Gamma) spec ( Γ ) , is the multiset of eigenvalues of A ( Γ ) A(\Gamma) A ( Γ ) (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) spec ( Γ ) 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 E λ denote the orthogonal projection matrix associated with the λ \lambda λ -eigenspace of A ( Γ ) A(\Gamma) A ( Γ ) . The (eigenvalue) support of vertex u u u in Γ \Gamma Γ , denoted Φ u ( Γ ) \Phi_u(\Gamma) Φ u ( Γ ) , is the set
Φ u ( Γ ) = { λ ∈ σ ( Γ ) : ( E λ ) u , u ≠ 0 } . \Phi_u(\Gamma) = \{\lambda\in\sigma(\Gamma) : (E_\lambda)_{u,u} \ne0\}. Φ u ( Γ ) = { λ ∈ σ ( Γ ) : ( E λ ) u , u = 0 } .
If Γ \Gamma Γ is clear from the context, then we write Φ u ( Γ ) \Phi_u(\Gamma) Φ u ( Γ ) as Φ u \Phi_u Φ u . We also remark that λ ∈ Φ u ( Γ ) \lambda\in\Phi_u(\Gamma) λ ∈ Φ u ( Γ ) if and only if there is an eigenvector w \mathbf{w} w for Γ \Gamma Γ associated with λ \lambda λ that has a nonzero u u u th entry.
We write M T M^T M T and M ∗ M^* M ∗ for the transpose and conjugate transpose of a matrix M M M . We let I m I_m I m , O m O_m O m , J m J_m J m denote the m × m m \times m m × 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 m m m vertices by O m O_m O m , K m K_m K m , and P m P_m P m , respectively, and the complete bipartite graph with parts of size r r r and s s s by K r , s K_{r,s} K r , s . We write Γ 1 ≅ Γ 2 \Gamma_1 \cong\Gamma_2 Γ 1 ≅ Γ 2 to denote that Γ 1 \Gamma_1 Γ 1 and Γ 2 \Gamma_2 Γ 2 are isomorphic graphs. We also denote the automorphism group of Γ \Gamma Γ by Aut ( Γ ) \operatorname{Aut}(\Gamma) Aut ( Γ ) .
Next, we review a few basic graph operations. Let Γ 1 \Gamma_1 Γ 1 and Γ 2 \Gamma_2 Γ 2 be two graphs. Let ⊕ \oplus ⊕ and ⊗ \otimes ⊗ denote the direct sum and Kronecker product on matrices. The union of Γ 1 \Gamma_1 Γ 1 and Γ 2 \Gamma_2 Γ 2 , denoted Γ 1 ⊔ Γ 2 \Gamma_1 \sqcup\Gamma_2 Γ 1 ⊔ Γ 2 , is the graph with vertex set V ( Γ 1 ) ∪ V ( Γ 2 ) V(\Gamma_1) \cup V(\Gamma_2) V ( Γ 1 ) ∪ V ( Γ 2 ) and adjacency matrix A ( Γ 1 ) ⊕ A ( Γ 2 ) A(\Gamma_1) \oplus A(\Gamma_2) A ( Γ 1 ) ⊕ A ( Γ 2 ) . The direct product , Cartesian product , and wreath product of Γ 1 \Gamma_1 Γ 1 and Γ 2 \Gamma_2 Γ 2 , denoted Γ 1 × Γ 2 \Gamma_1 \times\Gamma_2 Γ 1 × Γ 2 , Γ 1 □ Γ 2 \Gamma_1 \square\Gamma_2 Γ 1 □ Γ 2 , and Γ 1 [ Γ 2 ] \Gamma_1[\Gamma_2] Γ 1 [ Γ 2 ] , are the graphs with vertex set V ( Γ 1 ) × V ( Γ 2 ) V(\Gamma_1) \times V(\Gamma_2) V ( Γ 1 ) × V ( Γ 2 ) and adjacency matrices
A ( Γ 1 ) ⊗ A ( Γ 2 ) , A ( Γ 1 ) ⊗ I + I ⊗ A ( Γ 2 ) , and A ( Γ 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), A ( Γ 1 ) ⊗ A ( Γ 2 ) , A ( Γ 1 ) ⊗ I + I ⊗ A ( Γ 2 ) , and A ( Γ 1 [ Γ 2 ]) = A ( Γ 1 ) ⊗ J + I ⊗ A ( Γ 2 ) ,
respectively, where I I I and J J J are the identity and all-ones square matrices of appropriate sizes. We denote the union, direct product and Cartesian product of k k k copies of Γ \Gamma Γ by ⨆ k Γ \bigsqcup_k \Gamma ⨆ k Γ , Γ × k \Gamma^{\times k} Γ × k , and Γ □ k \Gamma^{\square k} Γ □ k , respectively. The complement of Γ \Gamma Γ , denoted Γ ‾ \overline{\Gamma} Γ , is the graph with V ( Γ ) = V ( Γ ‾ ) V(\Gamma) = V(\overline{\Gamma}) V ( Γ ) = V ( Γ ) and
A ( Γ ‾ ) = J − I − A ( Γ ) . A(\overline{\Gamma}) = J - I - A(\Gamma). A ( Γ ) = J − I − A ( Γ ) .
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} spec ( Γ 1 ⊔ Γ 2 ) spec ( Γ 1 × Γ 2 ) spec ( Γ 1 □ Γ 2 ) = spec ( Γ 1 ) ∪ spec ( Γ 2 ) , = { λ μ : λ ∈ spec ( Γ 1 ) , μ ∈ spec ( Γ 2 )} , = { λ + μ : λ ∈ spec ( Γ 1 ) , μ ∈ spec ( Γ 2 )} . (3)
If we further assume that Γ 2 \Gamma_2 Γ 2 is regular with valency d d d , then
spec ( Γ 1 [ Γ 2 ] ) = { λ ∣ V ( Γ 2 ) ∣ + d : λ ∈ spec ( Γ 1 ) } ∪ j = 1 ∣ V ( Γ 1 ) ∣ { μ : μ ∈ spec ( Γ 2 ) ∖ { d } } (4) \operatorname{spec}(\Gamma_1[\Gamma_2]) = \{\lambda|V(\Gamma_2)|+d: \lambda\in\operatorname{spec}(\Gamma_1)\} \mathbin{\mathop{\cup}\limits_{j=1}^{|V(\Gamma_1)|}} \{\mu: \mu\in\operatorname{spec}(\Gamma_2) \setminus\{d\}\} \tag*{(4)} spec ( Γ 1 [ Γ 2 ]) = { λ ∣ V ( Γ 2 ) ∣ + d : λ ∈ spec ( Γ 1 )} j = 1 ∪ ∣ V ( Γ 1 ) ∣ { μ : μ ∈ spec ( Γ 2 ) ∖ { d }} (4)
where the union here is taken with respect to multisets.
Finally, we discuss periodicity and its relation to sedentariness. A set S ⊆ R S \subseteq\mathbb{R} S ⊆ R with ∣ S ∣ ≥ 2 |S| \ge2 ∣ S ∣ ≥ 2 satisfies the ratio condition if a − b c − d ∈ Q \frac{a-b}{c-d} \in\mathbb{Q} c − d a − b ∈ Q for all a , b , c , d ∈ S a,b,c,d \in S a , b , c , d ∈ S with c ≠ d c \ne d c = d . A non-isolated vertex u u u of Γ \Gamma Γ is periodic if ∣ U ( τ ) u , u ∣ = 1 |U(\tau)_{u,u}| = 1 ∣ U ( τ ) u , u ∣ = 1 for some τ > 0 \tau> 0 τ > 0 . The minimum such τ \tau τ is called the (minimum) period of vertex u u u in Γ \Gamma Γ , denoted by ρ \rho ρ . It is known that vertex u u u is periodic if and only if Φ u \Phi_u Φ u satisfies the ratio condition [13 ] . We say that Γ \Gamma Γ is a periodic graph if every vertex in Γ \Gamma Γ is periodic at the same time. The fact below, derived from Lemmas 9 and 12 in [25 ] , implies that the infimum in (1.2) is attained for a periodic vertex.
Proposition 2.1. Let u u u be a periodic vertex with period ρ \rho ρ . The following are equivalent.
(1) Vertex u u u is sedentary in Γ \Gamma Γ .
(2) For all t ∈ [ 0 , ρ ] t \in[0,\rho] t ∈ [ 0 , ρ ] , U ( t ) u , u ≠ 0 U(t)_{u,u} \ne0 U ( t ) u , u = 0 .
(3) We have C = min t ∈ [ 0 , ρ ] ∣ U ( t ) u , u ∣ > 0 \mathcal{C} = \min_{t \in[0,\rho]} |U(t)_{u,u}| > 0 C = min t ∈ [ 0 , ρ ] ∣ U ( t ) u , u ∣ > 0 .
We now state [25 Corollary 13(1)] , which says that vertex u u u is sedentary whenever the u u u th diagonal entry of some E λ E_\lambda E λ is sufficiently large. We let ν 2 ( a ) \nu_2(a) ν 2 ( a ) denote the largest power of two that divides an integer a a a . We adopt the convention that ν 2 ( 0 ) = + ∞ \nu_2(0) = +\infty ν 2 ( 0 ) = + ∞ .
Theorem 2.2. Let u u u be a vertex in Γ \Gamma Γ and fix λ ∈ Φ u \lambda\in\Phi_u λ ∈ Φ u . The following hold.
(1) If ( E λ ) u , u > 1 2 (E_\lambda)_{u,u} > \frac{1}{2} ( E λ ) u , u > 2 1 , then u u u is sedentary with ∣ U ( t ) u , u ∣ ≥ 2 ( E λ ) u , u − 1 |U(t)_{u,u}| \ge2(E_\lambda)_{u,u} - 1 ∣ U ( t ) u , u ∣ ≥ 2 ( E λ ) u , u − 1 .
(2) Let ( E λ ) u , u = 1 2 (E_\lambda)_{u,u} = \frac{1}{2} ( E λ ) u , u = 2 1 . Then u u u is sedentary if and only if there are integers ℓ μ \ell_\mu ℓ μ such that
∑ μ ∈ Φ u ∖ { λ } ℓ μ ( μ − λ ) = 0 and ∑ μ ∈ Φ u ∖ { λ } ℓ μ is odd . (5) \sum_{\mu\in\Phi_u \setminus\{\lambda\}} \ell_\mu(\mu-\lambda)=0
\quad\text{and}\quad
\sum_{\mu\in\Phi_u \setminus\{\lambda\}} \ell_\mu\text{ is odd}. \tag*{(5)} μ ∈ Φ u ∖ { λ } ∑ ℓ μ ( μ − λ ) = 0 and μ ∈ Φ u ∖ { λ } ∑ ℓ μ is odd . (5) Additionally, if u u u is periodic, then u u u is sedentary if and only if ν 2 ( μ − λ Δ ) \nu_2\left(\frac{\mu-\lambda}{\sqrt{\Delta}}\right) ν 2 ( Δ μ − λ ) are not all equal for all μ ∈ Φ u ∖ { λ } \mu\in\Phi_u \setminus\{\lambda\} μ ∈ Φ u ∖ { λ } , where Δ = 1 \Delta= 1 Δ = 1 if Φ u ⊆ Z \Phi_u \subseteq\mathbb{Z} Φ u ⊆ Z and Δ > 1 \Delta> 1 Δ > 1 is a square-free integer determined from Φ u \Phi_u Φ u otherwise.
Twin Vertices
In this section, we gather known facts about twin vertices that are useful in later sections.
Let N Γ ( u ) N_\Gamma(u) N Γ ( u ) denote the set of neighbors of vertex u u u in Γ \Gamma Γ . Two vertices u u u and v v v are twins if N Γ ( u ) ∖ { u , v } = N Γ ( v ) ∖ { u , v } N_\Gamma(u) \setminus\{u,v\} = N_\Gamma(v) \setminus\{u,v\} N Γ ( u ) ∖ { u , v } = N Γ ( v ) ∖ { u , v } . Further, if u u u and v v v are adjacent, then they are called true twins ; otherwise, they are called false twins . The following lemma is evident.
Lemma 3.1. Let X 1 , X 2 ⊆ V ( Γ ) X_1, X_2 \subseteq V(\Gamma) X 1 , X 2 ⊆ V ( Γ ) . If all elements of X 1 , X 2 X_1, X_2 X 1 , X 2 are pairwise true (resp., false ) twins and X 1 ∩ X 2 ≠ ∅ X_1 \cap X_2 \ne\varnothing X 1 ∩ X 2 = ∅ , then all elements of X 1 ∪ X 2 X_1 \cup X_2 X 1 ∪ X 2 are pairwise true (resp., false ) twins.
So, if Γ \Gamma Γ contains a vertex u u u with a true (resp., false) twin, then we can find the largest subset X ⊆ V ( Γ ) X \subseteq V(\Gamma) X ⊆ V ( Γ ) such that u ∈ X u \in X u ∈ X and all elements of X X X are pairwise true (resp., false) twins. A subset X ⊂ V ( Γ ) X \subset V(\Gamma) X ⊂ V ( Γ ) is a twin set if it is a maximal set in which N Γ ( u ) ∖ { u , v } = N Γ ( v ) ∖ { u , v } N_{\Gamma}(u)\setminus\{u,v\}=N_{\Gamma}(v)\setminus\{u,v\} N Γ ( u ) ∖ { u , v } = N Γ ( v ) ∖ { u , v } for all pairs u , v ∈ X u,v \in X u , v ∈ X . In particular, if X X X contains adjacent vertices, then X X X is a true twin set , and if no vertices in X X X are adjacent, then it is a false twin set . Note that X X X is a true twin set in Γ \Gamma Γ if and only if X X X is a false twin set in the complement of Γ \Gamma Γ . The following lemma will also be useful later on.
Lemma 3.2. Let f ∈ Aut ( Γ ) f \in\operatorname{Aut}(\Gamma) f ∈ Aut ( Γ ) . Then X ⊆ V ( Γ ) X \subseteq V(\Gamma) X ⊆ V ( Γ ) is a twin set if and only if f ( X ) f(X) f ( X ) is.
Next, we state a characterization of twin vertices ([24 Lemma 2.9] and [26 Theorem 3] ).
Lemma 3.3. Let X X X be a twin set in Γ \Gamma Γ with u ∈ X u \in X u ∈ X . The vertex v v v belongs to X X X if and only if e u − e v \mathbf{e}_u-\mathbf{e}_v e u − e v is an eigenvector for Γ \Gamma Γ associated with the eigenvalue θ \theta θ , where θ = − 1 \theta=-1 θ = − 1 if u u u and v v v are true twins, and θ = 0 \theta=0 θ = 0 otherwise. Moreover, if m = ∣ X ∣ m=|X| m = ∣ X ∣ , then
E θ = ( ( I m − 1 m J m ) ⊕ O n − m ) + F , (6) E_{\theta}=\left(\left(I_m-\frac{1}{m}J_m\right)\oplus O_{n-m}\right)+F, \tag*{(6)} E θ = ( ( I m − m 1 J m ) ⊕ O n − m ) + F , (6) where rank F = m θ − ( m − 1 ) \operatorname{rank} F=m_{\theta}-(m-1) rank F = m θ − ( m − 1 ) , F ( e u − e v ) = 0 F(\mathbf{e}_u-\mathbf{e}_v)=\mathbf{0} F ( e u − e v ) = 0 for all u , v ∈ X u,v \in X u , v ∈ X and F F F is absent if m θ = m − 1 m_{\theta}=m-1 m θ = m − 1 , where m θ m_{\theta} m θ is the multiplicity of θ \theta θ .
From the above lemma, it follows that θ ∈ Φ u \theta\in\Phi_u θ ∈ Φ u whenever u u u belongs to a twin set.
The next result establishes a dichotomous relationship between PGST and sedentariness involving twins in a graph. It follows by combining [26 Corollary 1] and the fact that PST and PGST are equivalent for periodic vertices [32 ] .
Theorem 3.4. Let X X X be a twin set in Γ \Gamma Γ . Then a vertex in X X X is either sedentary or involved in PGST with another vertex in X X X . Additionally, if a vertex in X X X is periodic, then it is either sedentary or involved in PST with another vertex in X X X .
We now state a characterization of sedentary twin vertices first established by Monterde (see Theorems 2 and 3 in [26 ] ). We provide a proof for completeness.
Theorem 3.5. Let X X X be a twin set in Γ \Gamma Γ and consider the eigenvalue θ \theta θ and the matrix F F F in Lemma 3.3 . Then each vertex in X X X is sedentary if and only if one of the following holds.
(1) ∣ X ∣ ≥ 3 |X| \ge3 ∣ X ∣ ≥ 3 .
(2) X = { u , v } X=\{u,v\} X = { u , v } and a θ \theta θ -eigenvector w \mathbf{w} w orthogonal to e u − e v \mathbf{e}_u-\mathbf{e}_v e u − e v satisfies w T e u ≠ 0 \mathbf{w}^{\mathsf{T}}\mathbf{e}_u\ne0 w T e u = 0 .
(3) X = { u , v } X=\{u,v\} X = { u , v } , θ \theta θ is a simple eigenvalue of Γ \Gamma Γ , and condition (2.3) in Theorem 2.2 holds.
(4) X = { u , v } X=\{u,v\} X = { u , v } , any θ \theta θ -eigenvector w \mathbf{w} w orthogonal to e u − e v \mathbf{e}_u-\mathbf{e}_v e u − e v satisfies w T e u = w T e v = 0 \mathbf{w}^{\mathsf{T}}\mathbf{e}_u=\mathbf{w}^{\mathsf{T}}\mathbf{e}_v=0 w T e u = w T e v = 0 , and condition (2.3) in Theorem 2.2 holds.
Moreover, if u ∈ X u \in X u ∈ X and condition (1) or (2) holds, then ∣ U ( t ) u , u ∣ ≥ 1 − 2 ∣ X ∣ + 2 F u , u |U(t)_{u,u}|\ge1-\frac{2}{|X|}+2F_{u,u} ∣ U ( t ) u , u ∣ ≥ 1 − ∣ X ∣ 2 + 2 F u , u for all t ∈ R t\in\mathbb{R} t ∈ R , where F F F is given in (3.1).
Proof. Let X X X be a twin set in Γ \Gamma Γ . If (1) or (2) holds, then each vertex in X X X is sedentary by [26 Theorem 3] . Now, if (3) or (4) holds, then condition (2.3) in Theorem 2.2 holds, and so each vertex in X X X is sedentary by Theorem 2.2 (2). Finally, if X = { u , v } X=\{u,v\} X = { u , v } , any θ \theta θ -eigenvector w \mathbf{w} w orthogonal to e u − e v \mathbf{e}_u-\mathbf{e}_v e u − e v satisfies w T e u = w T e v = 0 \mathbf{w}^{\mathsf{T}}\mathbf{e}_u=\mathbf{w}^{\mathsf{T}}\mathbf{e}_v=0 w T e u = w T e v = 0 , and condition (2.3) in Theorem 2.2 does not hold, then u u u and v v v admit PGST in Γ \Gamma Γ by [20 Theorem 14] . Thus, u u u is not sedentary by Theorem 3.4 . This proves the above characterization. □
For the matrix F F F in (6) , it is clear from its construction in [26 ] that F u , u > 0 F_{u,u}>0 F u , u > 0 whenever condition (2) in Theorem 3.5 is satisfied, while F u , u = 0 F_{u,u}=0 F u , u = 0 whenever θ \theta θ is a simple eigenvalue of Γ \Gamma Γ , or any θ \theta θ -eigenvector w \mathbf{w} w orthogonal to e u − e v \mathbf{e}_u-\mathbf{e}_v e u − e v satisfies w T e u = w T e v = 0 \mathbf{w}^{\mathsf{T}}\mathbf{e}_u=\mathbf{w}^{\mathsf{T}}\mathbf{e}_v=0 w T e u = w T e v = 0 .
From [20 Theorem 11] , we deduce the following result concerning twins with PST whose supports consist of all integers.
Theorem 3.6. If PST occurs between twin vertices u u u and v v v such that Φ u ⊆ Z \Phi_u\subseteq\mathbb{Z} Φ u ⊆ Z , then ν 2 ( λ − θ ) \nu_2(\lambda-\theta) ν 2 ( λ − θ ) is constant for all λ ∈ Φ u ∖ { θ } \lambda\in\Phi_u\setminus\{\theta\} λ ∈ Φ u ∖ { θ } , where θ \theta θ is given in Lemma 3.3 .
Let Γ = Γ 1 [ Γ 2 ] \Gamma=\Gamma_1[\Gamma_2] Γ = Γ 1 [ Γ 2 ] where Γ 2 ∈ { O m , K m } \Gamma_2\in\{O_m,K_m\} Γ 2 ∈ { O m , K m } . Note that all the vertices in { ( u , j ) : j ∈ V ( Γ 2 ) } \{(u,j):j\in V(\Gamma_2)\} {( u , j ) : j ∈ V ( Γ 2 )} are twins in Γ \Gamma Γ for each u ∈ V ( Γ 1 ) u\in V(\Gamma_1) u ∈ V ( Γ 1 ) . Thus, each vertex in Γ \Gamma Γ belongs to a twin set of size at least m m m (indeed, it will belong to a twin set that has size an integer multiple of m m m ). Also, note that Γ \Gamma Γ is vertex-transitive if and only if Γ 1 \Gamma_1 Γ 1 is vertex-transitive. To determine the support of a vertex in Γ \Gamma Γ , note that 1 \mathbf{1} 1 is an eigenvector for Γ 2 \Gamma_2 Γ 2 associated with the eigenvalue d = 0 d=0 d = 0 if Γ 2 = O m \Gamma_2=O_m Γ 2 = O m , and the eigenvalue d = m − 1 d=m-1 d = m − 1 otherwise. If x \mathbf{x} x is an eigenvector for the eigenvalue λ \lambda λ of Γ 1 \Gamma_1 Γ 1 , then x ⊗ 1 \mathbf{x}\otimes\mathbf{1} x ⊗ 1 is an eigenvector for the eigenvalue m λ + d m\lambda+d mλ + d of Γ \Gamma Γ . Moreover, if y \mathbf{y} y is an eigenvector for the eigenvalue μ \mu μ of Γ 2 \Gamma_2 Γ 2 orthogonal to 1 \mathbf{1} 1 , then x ⊗ y \mathbf{x}\otimes\mathbf{y} x ⊗ y is an eigenvector for the eigenvalue μ \mu μ of Γ \Gamma Γ . Therefore,
Φ ( u , j ) ( Γ ) = { { m λ : λ ∈ Φ u ( Γ 1 ) } ∪ { 0 } , if Γ 2 = O m , { m λ + ( m − 1 ) : λ ∈ Φ u ( Γ 1 ) } ∪ { − 1 } , if Γ 2 = K m . (7) \Phi_{(u,j)}(\Gamma)=
\begin{cases}
\{m\lambda:\lambda\in\Phi_u(\Gamma_1)\}\cup\{0\}, & \text{if }\Gamma_2=O_m,\\
\{m\lambda+(m-1):\lambda\in\Phi_u(\Gamma_1)\}\cup\{-1\}, & \text{if }\Gamma_2=K_m.
\end{cases} \tag*{(7)} Φ ( u , j ) ( Γ ) = { { mλ : λ ∈ Φ u ( Γ 1 )} ∪ { 0 } , { mλ + ( m − 1 ) : λ ∈ Φ u ( Γ 1 )} ∪ { − 1 } , if Γ 2 = O m , if Γ 2 = K m . (7)
We use this fact to characterize the quantum state transfer properties of Γ \Gamma Γ .
Theorem 3.7. Let Γ = Γ 1 [ Γ 2 ] \Gamma=\Gamma_1[\Gamma_2] Γ = Γ 1 [ Γ 2 ] where Γ 2 ∈ { O m , K m } \Gamma_2\in\{O_m,K_m\} Γ 2 ∈ { O m , K m } and consider θ \theta θ in Lemma 3.3 .
(1) Vertex ( u , j ) (u,j) ( u , j ) is involved in PGST in Γ \Gamma Γ if and only if Γ 2 ∈ { K 2 , O 2 } \Gamma_2\in\{K_2,O_2\} Γ 2 ∈ { K 2 , O 2 } , θ ∉ Φ u ( Γ 1 ) \theta\notin\Phi_u(\Gamma_1) θ ∈ / Φ u ( Γ 1 ) , and for all integers ℓ λ \ell_\lambda ℓ λ , we have
∑ λ ∈ Φ ( u , j ) ( Γ ) ∖ { θ } ℓ λ ( λ − θ ) = 0 implies that ∑ λ ∈ Φ ( u , j ) ( Γ ) ∖ { θ } ℓ λ is even. (8) \sum_{\lambda\in\Phi_{(u,j)}(\Gamma)\setminus\{\theta\}}\ell_\lambda(\lambda-\theta)=0\ \text{ implies that }\ \sum_{\lambda\in\Phi_{(u,j)}(\Gamma)\setminus\{\theta\}}\ell_\lambda\ \text{ is even.} \tag*{(8)} λ ∈ Φ ( u , j ) ( Γ ) ∖ { θ } ∑ ℓ λ ( λ − θ ) = 0 implies that λ ∈ Φ ( u , j ) ( Γ ) ∖ { θ } ∑ ℓ λ is even. (8) (2) Vertex ( u , j ) (u,j) ( u , j ) is involved in PST in Γ \Gamma Γ if and only if Γ 2 ∈ { K 2 , O 2 } \Gamma_2\in\{K_2,O_2\} Γ 2 ∈ { K 2 , O 2 } , θ ∉ Φ u ( Γ 1 ) \theta\notin\Phi_u(\Gamma_1) θ ∈ / Φ u ( Γ 1 ) , λ − θ Δ \frac{\lambda-\theta}{\sqrt{\Delta}} Δ λ − θ is an integer for all λ ∈ Φ ( u , j ) ( Γ ) ∖ { θ } \lambda\in\Phi_{(u,j)}(\Gamma)\setminus\{\theta\} λ ∈ Φ ( u , j ) ( Γ ) ∖ { θ } where Δ = 1 \Delta=1 Δ = 1 if Φ ( u , j ) ( Γ ) ⊆ Z \Phi_{(u,j)}(\Gamma)\subseteq\mathbb{Z} Φ ( u , j ) ( Γ ) ⊆ Z and Δ > 1 \Delta>1 Δ > 1 is a square-free integer determined from Φ ( u , j ) ( Γ ) \Phi_{(u,j)}(\Gamma) Φ ( u , j ) ( Γ ) otherwise, and there is an integer a a a such that ν 2 ( λ − θ Δ ) = a \nu_2\left(\frac{\lambda-\theta}{\sqrt{\Delta}}\right)=a ν 2 ( Δ λ − θ ) = a for all λ ∈ Φ ( u , j ) ( Γ ) ∖ { θ } \lambda\in\Phi_{(u,j)}(\Gamma)\setminus\{\theta\} λ ∈ Φ ( u , j ) ( Γ ) ∖ { θ } . In this case, τ = π 2 a Δ \tau=\frac{\pi}{2^a\sqrt{\Delta}} τ = 2 a Δ π is a PST time.
Moreover, PGST or PST in Γ \Gamma Γ occurs between pairs of vertices in the same twin set.
Proof. The case when Γ 2 = O m \Gamma_2=O_m Γ 2 = O m is known, see Theorems 3 and 4 in [5 ] . The case Γ 2 = K m \Gamma_2=K_m Γ 2 = K m follows similarly using (7) and the same arguments used in Theorems 3 and 4 in [5 ] . □
Graphs of the form Γ = Γ 1 [ Γ 2 ] \Gamma=\Gamma_1[\Gamma_2] Γ = Γ 1 [ Γ 2 ] , where Γ 2 ∈ { K m , O m } \Gamma_2\in\{K_m,O_m\} Γ 2 ∈ { K m , O m } , are known in the literature as blow-up graphs , i.e. Γ \Gamma Γ is a graph obtained by either replacing every vertex of Γ 1 \Gamma_1 Γ 1 by a clique of size m m m , or replacing every vertex of Γ 1 \Gamma_1 Γ 1 by a coclique of size m m m ; then two vertices are adjacent if they belong to cliques, or cocliques that replaced vertices adjacent in Γ 1 \Gamma_1 Γ 1 . Quantum walks on blow-up graphs of the form Γ 1 [ O m ] \Gamma_1[O_m] Γ 1 [ O m ] were investigated in [5 , 27 ] . The following is immediate from Theorems 3.4 and 3.7 .
Corollary 3.8. Let Γ = Γ 1 [ Γ 2 ] \Gamma= \Gamma_1[\Gamma_2] Γ = Γ 1 [ Γ 2 ] where Γ 2 ∈ { O m , K m } \Gamma_2 \in\{O_m,K_m\} Γ 2 ∈ { O m , K m } and consider θ \theta θ in Lemma 3.3. Vertex ( u , j ) (u,j) ( u , j ) is sedentary in Γ \Gamma Γ if and only if one of the following conditions holds.
m ≥ 3 m \ge3 m ≥ 3 .
m = 2 m = 2 m = 2 and θ ∈ Φ u ( Γ 1 ) \theta\in\Phi_u(\Gamma_1) θ ∈ Φ u ( Γ 1 ) .
m = 2 m = 2 m = 2 , θ ∉ Φ u ( Γ 1 ) \theta\notin\Phi_u(\Gamma_1) θ ∈ / Φ u ( Γ 1 ) , and condition (3.3) does not hold.
m = 2 m = 2 m = 2 , θ ∉ Φ u ( Γ 1 ) \theta\notin\Phi_u(\Gamma_1) θ ∈ / Φ u ( Γ 1 ) , Φ ( u , j ) ( Γ ) \Phi_{(u,j)}(\Gamma) Φ ( u , j ) ( Γ ) satisfies the ratio condition, and the values of ν 2 ( λ − θ Δ ) \nu_2\left(\frac{\lambda-\theta}{\sqrt{\Delta}}\right) ν 2 ( Δ λ − θ ) are not constant for all λ ∈ Φ ( u , j ) ( Γ ) ∖ { θ } \lambda\in\Phi_{(u,j)}(\Gamma)\setminus\{\theta\} λ ∈ Φ ( u , j ) ( Γ ) ∖ { θ } .
To illustrate Theorem 3.7 and Corollary 3.8, we need the next lemma.
Lemma 3.9. If u ∈ V ( X ) u \in V(X) u ∈ V ( X ) and v ∈ V ( Y ) v \in V(Y) v ∈ V ( Y ) , then
Φ ( u , v ) ( X □ Y ) = { μ + η : μ ∈ Φ u ( X ) , η ∈ Φ v ( Y ) } . \Phi_{(u,v)}(X \mathbin{\Box} Y) = \{\mu+\eta: \mu\in\Phi_u(X), \eta\in\Phi_v(Y)\}. Φ ( u , v ) ( X □ Y ) = { μ + η : μ ∈ Φ u ( X ) , η ∈ Φ v ( Y )} . Proof. If λ ∈ σ ( X □ Y ) \lambda\in\sigma(X \mathbin{\Box} Y) λ ∈ σ ( X □ Y ) , then it is known that the spectral idempotent for λ \lambda λ is given by
F λ = ∑ μ + η = λ μ ∈ σ ( X ) , η ∈ σ ( Y ) E μ ⊗ E η . F_\lambda= \sum_{\substack{\mu+\eta=\lambda\\ \mu\in\sigma(X),\eta\in\sigma(Y)}} E_\mu\otimes E_\eta. F λ = μ + η = λ μ ∈ σ ( X ) , η ∈ σ ( Y ) ∑ E μ ⊗ E η . where E μ E_\mu E μ and E η E_\eta E η are spectral idempotents for μ ∈ σ ( X ) \mu\in\sigma(X) μ ∈ σ ( X ) and η ∈ σ ( Y ) \eta\in\sigma(Y) η ∈ σ ( Y ) , respectively. Thus, ( F λ ) ( u , v ) , ( u , v ) ≠ 0 (F_\lambda)_{(u,v),(u,v)} \ne0 ( F λ ) ( u , v ) , ( u , v ) = 0 if and only if at least one of the products ( E μ ) u , u ( E η ) v , v (E_\mu)_{u,u}(E_\eta)_{v,v} ( E μ ) u , u ( E η ) v , v is nonzero. Equivalently, μ ∈ Φ u ( X ) \mu\in\Phi_u(X) μ ∈ Φ u ( X ) and η ∈ Φ v ( Y ) \eta\in\Phi_v(Y) η ∈ Φ v ( Y ) .
Corollary 3.10. Let n ≥ 1 n \ge1 n ≥ 1 and v , w ∈ V ( P 3 □ n ) v,w \in V(P_3^{\Box n}) v , w ∈ V ( P 3 □ n ) such that w = ( a , … , a ) w=(a,\ldots,a) w = ( a , … , a ) , where a a a is the degree two vertex of P 3 P_3 P 3 . Then
Φ w ( P 3 □ n ) = { { ± 2 j 2 : j = 0 , 1 , … , n 2 } if n is even , { ± ( 2 j + 1 ) 2 : j = 0 , 1 , … , n − 1 2 } if n is odd . \Phi_w(P_3^{\Box n}) =
\begin{cases}
\{\pm2j\sqrt{2}:j=0,1,\ldots,\frac{n}{2}\} & \text{if } n \text{ is even},\\
\{\pm(2j+1)\sqrt{2}:j=0,1,\ldots,\frac{n-1}{2}\} & \text{if } n \text{ is odd}.
\end{cases} Φ w ( P 3 □ n ) = { { ± 2 j 2 : j = 0 , 1 , … , 2 n } { ± ( 2 j + 1 ) 2 : j = 0 , 1 , … , 2 n − 1 } if n is even , if n is odd . Moreover, if v ≠ w v \ne w v = w , then Φ v ( P 3 □ n ) \Phi_v(P_3^{\Box n}) Φ v ( P 3 □ n ) is equal to σ ( P 3 □ n ) = { ± j 2 : j = 0 , 1 , … , n } \sigma(P_3^{\Box n})=\{\pm j\sqrt{2}:j=0,1,\ldots,n\} σ ( P 3 □ n ) = { ± j 2 : j = 0 , 1 , … , n } .
Proof. Note that for all n ≥ 1 n \ge1 n ≥ 1 , we have σ ( P 3 □ n ) = { ± j 2 : j = 0 , 1 , … , n } \sigma(P_3^{\Box n})=\{\pm j\sqrt{2}:j=0,1,\ldots,n\} σ ( P 3 □ n ) = { ± j 2 : j = 0 , 1 , … , n } . Let a a a and b b b be degree two and degree one vertices of P 3 P_3 P 3 , respectively. Using the eigenvectors of P 3 P_3 P 3 , we get Φ a ( P 3 ) = { ± 2 } \Phi_a(P_3)=\{\pm\sqrt{2}\} Φ a ( P 3 ) = { ± 2 } and Φ b ( P 3 ) = { ± 2 , 0 } \Phi_b(P_3)=\{\pm\sqrt{2},0\} Φ b ( P 3 ) = { ± 2 , 0 } . Applying Lemma 3.9 to P 3 □ 2 = P 3 □ P 3 P_3^{\Box2}=P_3\Box P_3 P 3 □ 2 = P 3 □ P 3 gives us Φ ( a , a ) ( P 3 □ 2 ) = { ± 2 2 , 0 } \Phi_{(a,a)}(P_3^{\Box2})=\{\pm2\sqrt{2},0\} Φ ( a , a ) ( P 3 □ 2 ) = { ± 2 2 , 0 } and the support of any other vertex in P 3 □ 2 P_3^{\Box2} P 3 □ 2 is equal to σ ( P 3 □ 2 ) \sigma(P_3^{\Box2}) σ ( P 3 □ 2 ) . Using this fact and again applying Lemma 3.9 to P 3 □ 3 = P 3 □ 2 □ P 3 P_3^{\Box3}=P_3^{\Box2}\Box P_3 P 3 □ 3 = P 3 □ 2 □ P 3 , we get that Φ ( a , a , a ) ( P 3 □ 3 ) = { ± 3 2 , ± 2 } \Phi_{(a,a,a)}(P_3^{\Box3})=\{\pm3\sqrt{2},\pm\sqrt{2}\} Φ ( a , a , a ) ( P 3 □ 3 ) = { ± 3 2 , ± 2 } and the support of any other vertex in P 3 □ 3 P_3^{\Box3} P 3 □ 3 is equal to σ ( P 3 □ 3 ) \sigma(P_3^{\Box3}) σ ( P 3 □ 3 ) . One may then argue inductively to obtain the above result.
We now illustrate Theorem 3.7 and Corollary 3.8 in the next examples. For any graph X X X , each vertex in X [ O m ] X[O_m] X [ O m ] belongs to a twin set of size at least m m m . Thus, if m ≥ 3 m \ge3 m ≥ 3 , then Corollary 3.8(1) implies that X [ O m ] X[O_m] X [ O m ] is sedentary. Hence, we only deal with examples where m = 2 m=2 m = 2 .
Example 3.11. K 1 , n [ O 2 ] K_{1,n}[O_2] K 1 , n [ O 2 ] with n ≥ 2 n \ge2 n ≥ 2 .
Let n ≥ 2 n \ge2 n ≥ 2 . Consider K 1 , n K_{1,n} K 1 , n with central vertex u 0 u_0 u 0 , and leaf vertices v 1 , … , v n v_1,\ldots,v_n v 1 , … , v n . Then
Φ u 0 ( K 1 , n ) = { ± n } and Φ v j ( K 1 , n ) = { ± n , 0 } . \Phi_{u_0}(K_{1,n})=\{\pm\sqrt{n}\} \quad\text{and}\quad\Phi_{v_j}(K_{1,n})=\{\pm\sqrt{n},0\}. Φ u 0 ( K 1 , n ) = { ± n } and Φ v j ( K 1 , n ) = { ± n , 0 } .
Thus, for each vertex ( w , j ) (w,j) ( w , j ) of ( K 1 , n ) [ O 2 ] (K_{1,n})[O_2] ( K 1 , n ) [ O 2 ] , the set Φ ( w , j ) ( K 1 , n [ O 2 ] ) = { ± 2 n , 0 } \Phi_{(w,j)}(K_{1,n}[O_2])=\{\pm2\sqrt{n},0\} Φ ( w , j ) ( K 1 , n [ O 2 ]) = { ± 2 n , 0 } satisfies the ratio condition. In this example, we have θ = 0 \theta=0 θ = 0 and ν 2 ( λ − θ n ) = 1 \nu_2\left(\frac{\lambda-\theta}{\sqrt{n}}\right)=1 ν 2 ( n λ − θ ) = 1 for all λ ∈ Φ ( w , j ) ( K 1 , n [ O 2 ] ) ∖ { 0 } \lambda\in\Phi_{(w,j)}(K_{1,n}[O_2])\setminus\{0\} λ ∈ Φ ( w , j ) ( K 1 , n [ O 2 ]) ∖ { 0 } . By Corollary 3.8(2), each ( v ℓ , j ) (v_\ell,j) ( v ℓ , j ) is sedentary in K 1 , n [ O 2 ] K_{1,n}[O_2] K 1 , n [ O 2 ] . Meanwhile, vertices ( u 0 , 1 ) (u_0,1) ( u 0 , 1 ) and ( u 0 , 2 ) (u_0,2) ( u 0 , 2 ) admit PST in K 1 , n [ O 2 ] K_{1,n}[O_2] K 1 , n [ O 2 ] at time π 2 n \frac{\pi}{2\sqrt{n}} 2 n π by Theorem 3.7(2).
Example 3.12. P 3 □ n [ O 2 ] P_3^{\square n}[O_2] P 3 □ n [ O 2 ] with n ≥ 1 n \ge1 n ≥ 1 (see Figure 1 for P 3 [ O 2 ] P_3[O_2] P 3 [ O 2 ] ). Let u ∈ V ( P 3 □ n ) u \in V(P_3^{\square n}) u ∈ V ( P 3 □ n ) . First, suppose n n n is odd and u = ( a , … , a ) u=(a,\ldots,a) u = ( a , … , a ) where a a a is the degree two vertex of P 3 P_3 P 3 . Then by Corollary 3.10, we have
Figure 1. P 3 [ O 2 ] P_3[O_2] P 3 [ O 2 ] admits PST at time π 2 2 \frac{\pi}{2\sqrt{2}} 2 2 π between false twin vertices marked pink (left); ( K 2 □ K 1 , 2 ) [ K 2 ] (K_2\square K_{1,2})[K_2] ( K 2 □ K 1 , 2 ) [ K 2 ] admits PGST between pairs of true twin vertices marked pink (right). All blue vertices are sedentary in both graphs.
Φ u ( P 3 □ n ) = { ± ( 2 ℓ + 1 ) 2 : ℓ = 0 , 1 , … , n − 1 2 } , \Phi_u(P_3^{\square n})=\{\pm(2\ell+1)\sqrt{2}:\ell=0,1,\ldots,\frac{n-1}{2}\}, Φ u ( P 3 □ n ) = { ± ( 2 ℓ + 1 ) 2 : ℓ = 0 , 1 , … , 2 n − 1 } ,
and so 0 ∉ Φ u ( P 3 □ n ) 0\notin\Phi_u(P_3^{\square n}) 0 ∈ / Φ u ( P 3 □ n ) . We have Φ ( u , 1 ) ( P 3 □ n [ O 2 ] ) = { ± 2 ( 2 ℓ + 1 ) 2 : ℓ = 0 , 1 , … , n − 1 2 } ∪ { θ = 0 } \Phi_{(u,1)}(P_3^{\square n}[O_2])=\{\pm2(2\ell+1)\sqrt{2}:\ell=0,1,\ldots,\frac{n-1}{2}\}\cup\{\theta=0\} Φ ( u , 1 ) ( P 3 □ n [ O 2 ]) = { ± 2 ( 2 ℓ + 1 ) 2 : ℓ = 0 , 1 , … , 2 n − 1 } ∪ { θ = 0 } , and so Φ ( u , 1 ) ( P 3 □ n [ O 2 ] ) \Phi_{(u,1)}(P_3^{\square n}[O_2]) Φ ( u , 1 ) ( P 3 □ n [ O 2 ]) satisfies the ratio condition and ν 2 ( λ − θ 2 ) \nu_2\left(\frac{\lambda-\theta}{\sqrt{2}}\right) ν 2 ( 2 λ − θ ) is a constant equal to 1. Invoking Theorem 3.7[2 ] , we obtain PST between ( u , 1 ) (u,1) ( u , 1 ) and its twin in P 3 □ n [ O 2 ] P_3^{\square n}[O_2] P 3 □ n [ O 2 ] at time π 2 2 \frac{\pi}{2\sqrt{2}} 2 2 π .
If n n n is even or u ≠ ( a , … , a ) u\ne(a,\ldots,a) u = ( a , … , a ) where a a a is the degree two vertex of P 3 P_3 P 3 , then 0 ∈ Φ u ( P 3 □ n ) 0\in\Phi_u(P_3^{\square n}) 0 ∈ Φ u ( P 3 □ n ) by Corollary 3.10. Thus, vertex ( u , j ) (u,j) ( u , j ) in P 3 □ n [ O 2 ] P_3^{\square n}[O_2] P 3 □ n [ O 2 ] for j ∈ { 1 , 2 } j\in\{1,2\} j ∈ { 1 , 2 } is sedentary by Corollary 3.8[2 ] .
Example 3.13. ( K k □ K 1 , n ) [ K 2 ] (K_k\square K_{1,n})[K_2] ( K k □ K 1 , n ) [ K 2 ] for k , n ≥ 2 k,n\ge2 k , n ≥ 2 (see Figure 1 for ( K 2 □ K 1 , 2 ) [ K 2 ] (K_2\square K_{1,2})[K_2] ( K 2 □ K 1 , 2 ) [ K 2 ] ).
In this example we are taking the wreath product with a complete graph so θ = − 1 \theta=-1 θ = − 1 . Let w j = ( a , v j ) w_j=(a,v_j) w j = ( a , v j ) be a vertex of K k □ K 1 , n K_k\square K_{1,n} K k □ K 1 , n , where v j v_j v j is not the central vertex of K 1 , n K_{1,n} K 1 , n . Then − 1 ∈ Φ w j ( K k □ K 1 , n ) -1\in\Phi_{w_j}(K_k\square K_{1,n}) − 1 ∈ Φ w j ( K k □ K 1 , n ) . By Corollary 3.8[2 ] , ( w j , 1 ) (w_j,1) ( w j , 1 ) and ( w j , 2 ) (w_j,2) ( w j , 2 ) are sedentary in ( K k □ K 1 , n ) [ K 2 ] (K_k\square K_{1,n})[K_2] ( K k □ K 1 , n ) [ K 2 ] .
Now, let w 0 = ( a , u 0 ) w_0=(a,u_0) w 0 = ( a , u 0 ) be a vertex of K k □ K 1 , n K_k\square K_{1,n} K k □ K 1 , n with u 0 u_0 u 0 as the central vertex of K 1 , n K_{1,n} K 1 , n . Then
Φ w 0 ( K k □ K 1 , n ) = { k + n − 1 , k − n − 1 , n − 1 , − n − 1 } . \Phi_{w_0}(K_k\square K_{1,n})=\{k+\sqrt{n}-1,k-\sqrt{n}-1,\sqrt{n}-1,-\sqrt{n}-1\}. Φ w 0 ( K k □ K 1 , n ) = { k + n − 1 , k − n − 1 , n − 1 , − n − 1 } .
Hence, for j ∈ { 1 , 2 } j\in\{1,2\} j ∈ { 1 , 2 } , Φ ( w 0 , j ) ( ( K k □ K 1 , n ) [ K 2 ] ) \Phi_{(w_0,j)}((K_k\square K_{1,n})[K_2]) Φ ( w 0 , j ) (( K k □ K 1 , n ) [ K 2 ]) is equal to
{ 2 ( k + n − 1 ) + 1 , 2 ( k − n − 1 ) + 1 , 2 ( n − 1 ) + 1 , 2 ( − n − 1 ) + 1 } ∪ { − 1 } . \{2(k+\sqrt{n}-1)+1,2(k-\sqrt{n}-1)+1,2(\sqrt{n}-1)+1,2(-\sqrt{n}-1)+1\}\cup\{-1\}. { 2 ( k + n − 1 ) + 1 , 2 ( k − n − 1 ) + 1 , 2 ( n − 1 ) + 1 , 2 ( − n − 1 ) + 1 } ∪ { − 1 } .
If n ∈ Z \sqrt{n}\in\mathbb{Z} n ∈ Z , then Φ ( w 0 , j ) ( ( K k □ K 1 , n ) [ K 2 ] ) \Phi_{(w_0,j)}((K_k\square K_{1,n})[K_2]) Φ ( w 0 , j ) (( K k □ K 1 , n ) [ K 2 ]) satisfies the ratio condition. Further, if k = n k=\sqrt{n} k = n , then − 1 ∈ Φ w 0 ( K k □ K 1 , n ) -1\in\Phi_{w_0}(K_k\square K_{1,n}) − 1 ∈ Φ w 0 ( K k □ K 1 , n ) , so ( w 0 , i ) (w_0,i) ( w 0 , i ) is sedentary in ( K k □ K 1 , n ) [ K 2 ] (K_k\square K_{1,n})[K_2] ( K k □ K 1 , n ) [ K 2 ] by Corollary 3.8[2 ] .
Now, suppose k ≠ n k\ne\sqrt{n} k = n . Here, we have − 1 ∉ Φ w 0 ( K k □ K 1 , n ) -1\notin\Phi_{w_0}(K_k\square K_{1,n}) − 1 ∈ / Φ w 0 ( K k □ K 1 , n ) , so we consider ν 2 ( λ − θ ) \nu_2(\lambda-\theta) ν 2 ( λ − θ ) where λ ∈ Φ ( w 0 , j ) ( ( K k □ K 1 , n ) [ K 2 ] ) ∖ { − 1 } \lambda\in\Phi_{(w_0,j)}((K_k\square K_{1,n})[K_2])\setminus\{-1\} λ ∈ Φ ( w 0 , j ) (( K k □ K 1 , n ) [ K 2 ]) ∖ { − 1 } . This is constant for all λ \lambda λ if and only if ν 2 ( k ) > ν 2 ( n ) \nu_2(k)>\nu_2(\sqrt{n}) ν 2 ( k ) > ν 2 ( n ) . Thus, if ν 2 ( k ) > ν 2 ( n ) \nu_2(k)>\nu_2(\sqrt{n}) ν 2 ( k ) > ν 2 ( n ) , then Theorem 3.7[2 ] implies that vertex ( w 0 , 1 ) (w_0,1) ( w 0 , 1 ) in ( K k □ K 1 , n ) [ K 2 ] (K_k\square K_{1,n})[K_2] ( K k □ K 1 , n ) [ K 2 ] admits PST with its twin at time π 2 g \frac{\pi}{2g} 2 g π where g = gcd ( k + n , k − n , n ) g=\gcd(k+\sqrt{n},k-\sqrt{n},\sqrt{n}) g = g cd( k + n , k − n , n ) . If ν 2 ( k ) ≤ ν 2 ( n ) \nu_2(k)\le\nu_2(\sqrt{n}) ν 2 ( k ) ≤ ν 2 ( n ) , then by Corollary 3.8[4 ] , vertex ( w 0 , i ) (w_0,i) ( w 0 , i ) is sedentary in ( K k □ K 1 , n ) [ K 2 ] (K_k\square K_{1,n})[K_2] ( K k □ K 1 , n ) [ K 2 ] for i ∈ { 1 , 2 } i\in\{1,2\} i ∈ { 1 , 2 } .
If n ∉ Z \sqrt{n}\notin\mathbb{Z} n ∈ / Z , then − 1 ∉ Φ w 0 ( K k □ K 1 , n ) -1\notin\Phi_{w_0}(K_k\square K_{1,n}) − 1 ∈ / Φ w 0 ( K k □ K 1 , n ) , so we consider condition (8) . Set
0 = ℓ 1 ( k + n ) + ℓ 2 ( k − n ) + ℓ 3 n − ℓ 4 n = ( ℓ 1 + ℓ 2 ) k + ( ℓ 1 − ℓ 2 + ℓ 3 − ℓ 4 ) n , 0=\ell_1(k+\sqrt{n})+\ell_2(k-\sqrt{n})+\ell_3\sqrt{n}-\ell_4\sqrt{n}=(\ell_1+\ell_2)k+(\ell_1-\ell_2+\ell_3-\ell_4)\sqrt{n}, 0 = ℓ 1 ( k + n ) + ℓ 2 ( k − n ) + ℓ 3 n − ℓ 4 n = ( ℓ 1 + ℓ 2 ) k + ( ℓ 1 − ℓ 2 + ℓ 3 − ℓ 4 ) n ,
where each ℓ j \ell_j ℓ j is an integer. As n ∉ Z \sqrt{n}\notin\mathbb{Z} n ∈ / Z , we get ℓ 1 + ℓ 2 = ℓ 1 − ℓ 2 + ℓ 3 − ℓ 4 = 0 \ell_1+\ell_2=\ell_1-\ell_2+\ell_3-\ell_4=0 ℓ 1 + ℓ 2 = ℓ 1 − ℓ 2 + ℓ 3 − ℓ 4 = 0 , and thus ℓ 1 + ℓ 2 + ℓ 3 + ℓ 4 = 2 ( ℓ 1 + ℓ 3 ) \ell_1+\ell_2+\ell_3+\ell_4=2(\ell_1+\ell_3) ℓ 1 + ℓ 2 + ℓ 3 + ℓ 4 = 2 ( ℓ 1 + ℓ 3 ) is always even. By Theorem 3.7[1 ] , PGST occurs between ( w 0 , 1 ) (w_0,1) ( w 0 , 1 ) and its twin in $(K_k\square K_{1,n})[K_2]`.
Walk-regular graphs
A graph Γ \Gamma Γ is k k k -regular if every vertex has degree k k k , this is equivalent to 1 1 1 being an k k k -eigenvector for Γ \Gamma Γ . If Γ \Gamma Γ is regular, the eigenvalues of Γ ‾ \overline{\Gamma} Γ can be determined from the eigenvalues of Γ \Gamma Γ . Let U Γ ( t ) U_{\Gamma}(t) U Γ ( t ) and U Γ ‾ ( t ) U_{\overline{\Gamma}}(t) U Γ ( t ) denote the transition matrices of Γ \Gamma Γ and Γ ‾ \overline{\Gamma} Γ , respectively. The following result is due to Godsil [14 Lemma 2.1] .
Lemma 4.1. If Γ \Gamma Γ is a regular graph on n n n vertices, then for all u , v ∈ V ( Γ ) u,v \in V(\Gamma) u , v ∈ V ( Γ ) ,
∣ U Γ ‾ ( t ) u , v − e − i t U Γ ( − t ) u , v ∣ ≤ 2 n for all t ∈ R . \left|U_{\overline{\Gamma}}(t)_{u,v}-e^{-it}U_{\Gamma}(-t)_{u,v}\right| \le\frac{2}{n}\quad\text{for all }t \in\mathbb{R}. U Γ ( t ) u , v − e − i t U Γ ( − t ) u , v ≤ n 2 for all t ∈ R .
Theorem 4.2. Let Γ \Gamma Γ be a regular graph on n n n vertices with vertex u u u that is C C C -sedentary. If C > 2 n C > \frac{2}{n} C > n 2 , then vertex u u u is ( C − 2 n ) (C-\frac{2}{n}) ( C − n 2 ) -sedentary in Γ ‾ \overline{\Gamma} Γ .
Proof. By assumption, ∣ U Γ ( − t ) u , u ∣ ≥ C \left|U_{\Gamma}(-t)_{u,u}\right| \ge C ∣ U Γ ( − t ) u , u ∣ ≥ C for all t ∈ R t \in\mathbb{R} t ∈ R . Since Γ \Gamma Γ is regular, Lemma 4.1 yields
∣ U Γ ‾ ( t ) u , u ∣ ≥ ∣ U Γ ( − t ) u , u ∣ − 2 n ≥ C − 2 n > 0 for all t ∈ R . \left|U_{\overline{\Gamma}}(t)_{u,u}\right| \ge\left|U_{\Gamma}(-t)_{u,u}\right|-\frac{2}{n} \ge C-\frac{2}{n}>0\quad\text{for all }t \in\mathbb{R}. U Γ ( t ) u , u ≥ ∣ U Γ ( − t ) u , u ∣ − n 2 ≥ C − n 2 > 0 for all t ∈ R .
A regular graph Γ \Gamma Γ is walk-regular if each nonnegative power of A ( Γ ) A(\Gamma) A ( Γ ) has a constant diagonal. Examples of walk-regular graphs include vertex-transitive graphs, Cayley graphs and graphs in association schemes (such as distance-regular graphs).
We will now show that for walk-regular graphs, the diagonal entries of U ( t ) U(t) U ( t ) can be written as a function in e i t e^{it} e i t .
Proposition 4.3. Let Γ \Gamma Γ be a walk-regular graph on n n n vertices. For any vertex u ∈ V ( Γ ) u \in V(\Gamma) u ∈ V ( Γ ) ,
U ( t ) u , u = 1 n ∑ j = 1 n e i λ j t for all t ∈ R . U(t)_{u,u}=\frac{1}{n}\sum_{j=1}^{n}e^{i\lambda_jt}\quad\text{for all }t \in\mathbb{R}. U ( t ) u , u = n 1 j = 1 ∑ n e i λ j t for all t ∈ R .
Proof. By definition, we have
U ( t ) = ∑ k = 0 ∞ ( i t ) k k ! A k for all t ∈ R . U(t)=\sum_{k=0}^{\infty}\frac{(it)^k}{k!}A^k\quad\text{for all }t \in\mathbb{R}. U ( t ) = k = 0 ∑ ∞ k ! ( i t ) k A k for all t ∈ R .
As Γ \Gamma Γ is walk-regular, A k A^k A k has constant diagonal for all k ≥ 0 k \ge0 k ≥ 0 . Thus, U ( t ) U(t) U ( t ) has constant diagonal for all t ∈ R t \in\mathbb{R} t ∈ R , and so U ( t ) u , u U(t)_{u,u} U ( t ) u , u is equal to 1 n \frac{1}{n} n 1 times the trace of U ( t ) U(t) U ( t ) . If λ 1 ≥ ⋯ ≥ λ n \lambda_1 \ge\cdots\ge\lambda_n λ 1 ≥ ⋯ ≥ λ n are the eigenvalues of Γ \Gamma Γ , then the eigenvalues of U ( t ) U(t) U ( t ) are e i λ j t e^{i\lambda_jt} e i λ j t , and so the conclusion follows.
Remark 4.4. If m λ m_\lambda m λ is the multiplicity of λ ∈ σ ( Γ ) \lambda\in\sigma(\Gamma) λ ∈ σ ( Γ ) , then for any vertex u ∈ V ( Γ ) u \in V(\Gamma) u ∈ V ( Γ ) , Proposition 4.3 yields
U ( t ) u , u = 1 n ∑ λ ∈ σ ( Γ ) m λ e i λ t for all t ∈ R . U(t)_{u,u}=\frac{1}{n}\sum_{\lambda\in\sigma(\Gamma)}m_\lambda e^{i\lambda t}\quad\text{for all }t \in\mathbb{R}. U ( t ) u , u = n 1 λ ∈ σ ( Γ ) ∑ m λ e iλ t for all t ∈ R .
Consequently, if Γ \Gamma Γ is walk-regular, since each E λ E_\lambda E λ is a polynomial in A ( Γ ) A(\Gamma) A ( Γ ) , each E λ E_\lambda E λ has constant diagonal. As the trace of E λ E_\lambda E λ is equal to the multiplicity m λ m_\lambda m λ of λ \lambda λ , we get that ( E λ ) u , u = m λ n > 0 (E_\lambda)_{u,u}=\frac{m_\lambda}{n}>0 ( E λ ) u , u = n m λ > 0 for all λ ∈ σ ( Γ ) \lambda\in\sigma(\Gamma) λ ∈ σ ( Γ ) , thus Φ u = σ ( Γ ) \Phi_u=\sigma(\Gamma) Φ u = σ ( Γ ) for all u ∈ V ( Γ ) u \in V(\Gamma) u ∈ V ( Γ ) .
From Proposition 4.3, the following is immediate.
Proposition 4.5. A walk-regular graph is sedentary if and only if one of its vertices is.
Let Γ 1 ∨ Γ 2 \Gamma_1 \vee\Gamma_2 Γ 1 ∨ Γ 2 denote the join of Γ 1 \Gamma_1 Γ 1 and Γ 2 \Gamma_2 Γ 2 , this is the graph obtained by taking one copy of each of Γ 1 \Gamma_1 Γ 1 and Γ 2 \Gamma_2 Γ 2 , and adding all edges between Γ 1 \Gamma_1 Γ 1 and Γ 2 \Gamma_2 Γ 2 . We remark there are regular graphs, that are not walk-regular and are sedentary. One example is Γ = ( ⨆ p K 3 ) ∨ ( ⨆ q K 4 ) \Gamma= (\bigsqcup_p K_3) \vee(\bigsqcup_q K_4) Γ = ( ⨆ p K 3 ) ∨ ( ⨆ q K 4 ) where 4 q − 3 p = 1 4q-3p=1 4 q − 3 p = 1 and p , q > 1 p,q>1 p , q > 1 . Here, each vertex of Γ \Gamma Γ belongs to a twin set of size at least three, which is sedentary by Theorem 3.5 (1). There are also regular but not walk-regular graphs that admit a subset W ⊆ V ( Γ ) W \subseteq V(\Gamma) W ⊆ V ( Γ ) such that each vertex in W W W is sedentary but each vertex in V ( Γ ) \ W V(\Gamma)\backslash W V ( Γ ) \ W is not sedentary. One example is Γ = ( ⨆ 2 p K 6 ) ∨ ( ⨆ 2 q K 2 ) \Gamma= (\bigsqcup_{2p} K_6) \vee(\bigsqcup_{2q} K_2) Γ = ( ⨆ 2 p K 6 ) ∨ ( ⨆ 2 q K 2 ) with 3 p − q = 1 3p-q=1 3 p − q = 1 , where the vertices that belong to ⨆ 2 p K 6 \bigsqcup_{2p} K_6 ⨆ 2 p K 6 are all sedentary in Γ \Gamma Γ by Theorem 3.5 (1), while those belonging to ⨆ 2 q K 2 \bigsqcup_{2q} K_2 ⨆ 2 q K 2 admit PST by [2 Theorem 2] (see also [19 Theorem 6] ).
By remark 4.4, we may restate Theorem 2.2 in the context of walk-regular graphs.
Corollary 4.6. Let Γ \Gamma Γ be a walk-regular graph and λ ∈ σ ( Γ ) \lambda\in\sigma(\Gamma) λ ∈ σ ( Γ ) .
(1) If m λ > n 2 m_\lambda> \frac{n}{2} m λ > 2 n , then Γ \Gamma Γ is sedentary with ∣ U ( t ) u , u ∣ ≥ 2 m λ n − 1 \lvert U(t)_{u,u}\rvert\ge\frac{2m_\lambda}{n}-1 ∣ U ( t ) u , u ∣ ≥ n 2 m λ − 1 .
(2) If m λ = n 2 m_\lambda= \frac{n}{2} m λ = 2 n , then Γ \Gamma Γ is sedentary if and only if condition (2) of Theorem 2.2 holds.
The complement of a walk-regular graph is walk-regular. The disjoint union of k k k copies of a walk-regular graph is also walk-regular. So, if Γ \Gamma Γ is a walk-regular graph, then so are Γ ‾ \overline{\Gamma} Γ and ⨆ k Γ \bigsqcup_k \Gamma ⨆ k Γ for all k ≥ 1 k \ge1 k ≥ 1 . This observation combined with Theorem 4.2 yields the following.
Corollary 4.7. Let Γ \Gamma Γ be a C C C -sedentary walk-regular graph on n n n vertices. If C > 2 n C > \frac{2}{n} C > n 2 , then ⨆ k Γ \bigsqcup_k \Gamma ⨆ k Γ is a ( C − 2 n ) (C-\frac{2}{n}) ( C − n 2 ) -sedentary walk-regular graph for all k ≥ 1 k \ge1 k ≥ 1 .
Integral graphs
We say that Γ \Gamma Γ is an integral graph if all of its eigenvalues are integers. By the ratio condition, an integral graph is periodic. Moreover, since the valency of a regular graph is an integer and the set of eigenvalues are algebraic integers, the ratio condition implies that a regular graph is periodic if and only if it is integral [9 ] .
The necklace polynomial of an integral graph
Inspired by Proposition 4.3 and recent works [18 , 23 ] , we introduce the notion of the necklace polynomial of an integral graph. We first recall the general framework for the definition of this polynomial. Let R = Z [ Z ∘ ] R = \mathbb{Z}[\mathbb{Z}^{\circ}] R = Z [ Z ∘ ] be the algebra associated with the monoid ( Z , × ) (\mathbb{Z},\times) ( Z , × ) . Elements of R R R are of the form ∑ m ∈ Z a m [ m ] \sum_{m\in\mathbb{Z}} a_m[m] ∑ m ∈ Z a m [ m ] where m ∈ Z m \in\mathbb{Z} m ∈ Z and a m ∈ Z a_m \in\mathbb{Z} a m ∈ Z . Addition and multiplication are defined naturally:
∑ m a m [ m ] + ∑ m b m [ m ] = ∑ m ( a m + b m ) [ m ] , [ m ] [ n ] = [ m n ] , \sum_m a_m[m] + \sum_m b_m[m] = \sum_m (a_m+b_m)[m], \qquad[m][n]=[mn], m ∑ a m [ m ] + m ∑ b m [ m ] = m ∑ ( a m + b m ) [ m ] , [ m ] [ n ] = [ mn ] ,
and extended linearly. If Γ \Gamma Γ is an integral graph with eigenvalues λ 1 ≥ ⋯ ≥ λ n \lambda_1 \ge\cdots\ge\lambda_n λ 1 ≥ ⋯ ≥ λ n , then we define
α Γ : = ∑ j = 1 n [ λ j ] ∈ R . \alpha_\Gamma:= \sum_{j=1}^{n}[\lambda_j] \in R. α Γ := j = 1 ∑ n [ λ j ] ∈ R .
Example 5.1. Since σ ( K n ) \sigma(K_n) σ ( K n ) is { n − 1 ( 1 ) , − 1 ( n − 1 ) } \{n-1^{(1)},-1^{(n-1)}\} { n − 1 ( 1 ) , − 1 ( n − 1 ) } , we have α K n = [ n − 1 ] + ( n − 1 ) [ − 1 ] \alpha_{K_n}=[n-1]+(n-1)[-1] α K n = [ n − 1 ] + ( n − 1 ) [ − 1 ] .
The following proposition is immediate from the spectra of graph products in (3) .
Proposition 5.2. Let Γ 1 , Γ 2 \Gamma_1,\Gamma_2 Γ 1 , Γ 2 be integral graphs. Then Γ 1 × Γ 2 \Gamma_1 \times\Gamma_2 Γ 1 × Γ 2 , Γ 1 ⊔ Γ 2 \Gamma_1 \sqcup\Gamma_2 Γ 1 ⊔ Γ 2 , and Γ 1 □ Γ 2 \Gamma_1 \mathbin{\Box}\Gamma_2 Γ 1 □ Γ 2 are integral graphs. Furthermore, α Γ 1 ⊔ Γ 2 = α Γ 1 + α Γ 2 \alpha_{\Gamma_1\sqcup\Gamma_2}=\alpha_{\Gamma_1}+\alpha_{\Gamma_2} α Γ 1 ⊔ Γ 2 = α Γ 1 + α Γ 2 and α Γ 1 × Γ 2 = α Γ 1 α Γ 2 \alpha_{\Gamma_1\times\Gamma_2}=\alpha_{\Gamma_1}\alpha_{\Gamma_2} α Γ 1 × Γ 2 = α Γ 1 α Γ 2 .
Given α ∈ Z [ Z ] \alpha\in\mathbb{Z}[\mathbb{Z}] α ∈ Z [ Z ] with α = ∑ m a m [ m ] \alpha= \sum_m a_m[m] α = ∑ m a m [ m ] , we define the necklace function associated with α \alpha α as
α ⋅ x = ∑ m a m x m . \alpha\cdot x = \sum_m a_m x^m. α ⋅ x = m ∑ a m x m .
Let m 0 m_0 m 0 be the minimal value of m m m appearing in α \alpha α . The necklace polynomial associated with α \alpha α is given by
α ^ ⋅ x = ∑ m a m x m − m 0 . \widehat{\alpha}\cdot x = \sum_m a_m x^{m-m_0}. α ⋅ x = m ∑ a m x m − m 0 .
Let z 0 ∈ C z_0 \in\mathbb{C} z 0 ∈ C such that ∣ z 0 ∣ = 1 |z_0| = 1 ∣ z 0 ∣ = 1 . We write ( α ⋅ x ) ( z 0 ) (\alpha\cdot x)(z_0) ( α ⋅ x ) ( z 0 ) for the evaluation of α ⋅ x \alpha\cdot x α ⋅ x at x = z 0 x=z_0 x = z 0 . This is a well-defined value. Note that z 0 z_0 z 0 is a root of ( α ⋅ x ) (\alpha\cdot x) ( α ⋅ x ) if and only if it is a root of α ^ ⋅ x \widehat{\alpha}\cdot x α ⋅ x .
Definition 5.3. Let Γ \Gamma Γ be an integral graph with eigenvalues λ 1 ≥ ⋯ ≥ λ n \lambda_1 \ge\cdots\ge\lambda_n λ 1 ≥ ⋯ ≥ λ n . The necklace polynomial N Γ ( x ) N_\Gamma(x) N Γ ( x ) of Γ \Gamma Γ is the necklace polynomial of α Γ \alpha_\Gamma α Γ . More concretely,
N Γ ( x ) = ∑ j = 1 n x λ j − λ n = x − λ n ∑ j = 1 n x λ j = x − λ n α Γ ( x ) . N_\Gamma(x) = \sum_{j=1}^{n} x^{\lambda_j-\lambda_n} = x^{-\lambda_n}\sum_{j=1}^{n}x^{\lambda_j}=x^{-\lambda_n}\alpha_\Gamma(x). N Γ ( x ) = j = 1 ∑ n x λ j − λ n = x − λ n j = 1 ∑ n x λ j = x − λ n α Γ ( x ) .
Example 5.4. If Γ = K n \Gamma=K_n Γ = K n , then N Γ ( x ) = x n + ( n − 1 ) N_\Gamma(x)=x^n+(n-1) N Γ ( x ) = x n + ( n − 1 ) .
Proposition 5.5. Let Γ \Gamma Γ be a connected, integral, walk-regular graph. Then N Γ ( x ) N_\Gamma(x) N Γ ( x ) is a monic polynomial of degree λ 1 − λ n \lambda_1-\lambda_n λ 1 − λ n . Furthermore N Γ ( 1 ) = ∣ V ( Γ ) ∣ N_\Gamma(1)=|V(\Gamma)| N Γ ( 1 ) = ∣ V ( Γ ) ∣ .
Let P ( x ) ∈ C [ x ] P(x)\in\mathbb{C}[x] P ( x ) ∈ C [ x ] be a polynomial of degree m m m . The reciprocal polynomial of P ( x ) P(x) P ( x ) is the polynomial P ⋆ ( x ) : = x m P ( 1 / x ) P^\star(x):=x^mP(1/x) P ⋆ ( x ) := x m P ( 1/ x ) . Note that the coefficients of P ⋆ ( x ) P^\star(x) P ⋆ ( x ) are the coefficients of P ( x ) P(x) P ( x ) in reverse order. Thus, P ( x ) P(x) P ( x ) and P ⋆ ( x ) P^\star(x) P ⋆ ( x ) have the same degree whenever P ( x ) P(x) P ( x ) has nonzero constant term. Also, observe that λ ∈ C ∖ { 0 } \lambda\in\mathbb{C}\setminus\{0\} λ ∈ C ∖ { 0 } is a root of P ( x ) P(x) P ( x ) if and only if 1 / λ 1/\lambda 1/ λ is a root of P ⋆ ( x ) P^\star(x) P ⋆ ( x ) . We say that P ( x ) P(x) P ( x ) is reciprocal if P ( x ) = P ⋆ ( x ) P(x)=P^\star(x) P ( x ) = P ⋆ ( x ) .
Lemma 5.6. N Γ ( x ) N_\Gamma(x) N Γ ( x ) is reciprocal if and only if Γ \Gamma Γ is a bipartite graph.
Proof. First, observe that
N Γ ⋆ ( x ) = x λ 1 − λ n ∑ j = 1 n ( 1 / x ) λ j − λ n = ∑ j = 1 n x λ 1 − λ j . N_\Gamma^\star(x)=x^{\lambda_1-\lambda_n}\sum_{j=1}^{n}(1/x)^{\lambda_j-\lambda_n}=\sum_{j=1}^{n}x^{\lambda_1-\lambda_j}. N Γ ⋆ ( x ) = x λ 1 − λ n j = 1 ∑ n ( 1/ x ) λ j − λ n = j = 1 ∑ n x λ 1 − λ j . Thus, N Γ ( x ) N_\Gamma(x) N Γ ( x ) is reciprocal if and only if λ 1 − λ j = λ n + 1 − j − λ n \lambda_1-\lambda_j=\lambda_{n+1-j}-\lambda_n λ 1 − λ j = λ n + 1 − j − λ n for all 1 ≤ j ≤ n 1\le j\le n 1 ≤ j ≤ n . That is, λ 1 + λ n = λ j + λ n + 1 − j \lambda_1+\lambda_n=\lambda_j+\lambda_{n+1-j} λ 1 + λ n = λ j + λ n + 1 − j for all 1 ≤ j ≤ n 1\le j\le n 1 ≤ j ≤ n . Since ∑ j = 1 n λ j = 0 \sum_{j=1}^{n}\lambda_j=0 ∑ j = 1 n λ j = 0 , the preceding equations hold if and only if λ j = − λ n + 1 − j \lambda_j=-\lambda_{n+1-j} λ j = − λ n + 1 − j for each 1 ≤ j ≤ n 1\le j\le n 1 ≤ j ≤ n . Equivalently, Γ \Gamma Γ is bipartite. □
The following result establishes a connection between the sedentariness of an integral walk-regular graph and the arithmetic properties of its necklace polynomial.
Theorem 5.7. Let Γ \Gamma Γ be an integral walk-regular graph. The following are equivalent.
Γ \Gamma Γ is sedentary.
N Γ ( x ) N_\Gamma(x) N Γ ( x ) has no roots on the unit circle.
N Γ ⋆ ( x ) N_\Gamma^\star(x) N Γ ⋆ ( x ) has no roots on the unit circle.
Proof. By assumption, Γ \Gamma Γ is periodic. Moreover, Proposition 4.3 implies that for all u ∈ V ( Γ ) u\in V(\Gamma) u ∈ V ( Γ ) ,
U ( t ) u , u = 1 n ∑ j = 1 n e i λ j t = 1 n ∑ j = 1 n z λ j = 1 n z λ n N Γ ( z ) U(t)_{u,u}=\frac{1}{n}\sum_{j=1}^{n}e^{i\lambda_jt}=\frac{1}{n}\sum_{j=1}^{n}z^{\lambda_j}=\frac{1}{n}z^{\lambda_n}N_\Gamma(z) U ( t ) u , u = n 1 j = 1 ∑ n e i λ j t = n 1 j = 1 ∑ n z λ j = n 1 z λ n N Γ ( z )
where z = exp ( i t ) z=\exp(it) z = exp ( i t ) . Suppose Γ \Gamma Γ is sedentary. As Γ \Gamma Γ is periodic, Proposition 2.1 (3) gives us C = min t ∈ [ 0 , 2 π ] ∣ U ( t ) u , u ∣ > 0 \mathcal{C}=\min_{t\in[0,2\pi]}|U(t)u,u|>0 C = min t ∈ [ 0 , 2 π ] ∣ U ( t ) u , u ∣ > 0 . Thus, ∣ U ( t ) u , u ∣ = ∣ N Γ ( z ) ∣ n ≥ C |U(t)u,u|=\frac{|N_{\Gamma}(z)|}{n}\ge\mathcal{C} ∣ U ( t ) u , u ∣ = n ∣ N Γ ( z ) ∣ ≥ C for all t ∈ [ 0 , 2 π ] t\in[0,2\pi] t ∈ [ 0 , 2 π ] , and so ∣ N Γ ( z ) ∣ ≥ C n > 0 |N_{\Gamma}(z)|\ge\mathcal{C}n>0 ∣ N Γ ( z ) ∣ ≥ C n > 0 for all ∣ z ∣ = 1 |z|=1 ∣ z ∣ = 1 . Hence, N Γ ( x ) N_{\Gamma}(x) N Γ ( x ) has no root on the unit circle. Conversely, suppose N Γ ( x ) N_{\Gamma}(x) N Γ ( x ) has no root on the unit circle. If U ( t 0 ) u , u = 0 U(t_0)u,u=0 U ( t 0 ) u , u = 0 for some t 0 ∈ [ 0 , 2 π ] t_0\in[0,2\pi] t 0 ∈ [ 0 , 2 π ] , then exp ( i t 0 ) \exp(it_0) exp ( i t 0 ) is a root of α ⋅ x \alpha\cdot x α ⋅ x , and hence, exp ( i t 0 ) \exp(it_0) exp ( i t 0 ) is a root of N Γ ( x ) N_{\Gamma}(x) N Γ ( x ) , a contradiction. Thus, U ( t ) u , u ≠ 0 U(t)u,u\ne0 U ( t ) u , u = 0 for all t ∈ [ 0 , ρ ] t\in[0,\rho] t ∈ [ 0 , ρ ] . Since Γ \Gamma Γ is periodic, Γ \Gamma Γ is sedentary by Proposition 2.1 (1). Thus, (1) and (2) are equivalent. The equivalence of (2) and (3) follows from the fact that a unit complex number α \alpha α is a root of N Γ ( x ) N_{\Gamma}(x) N Γ ( x ) if and only if 1 / α 1/\alpha 1/ α is a root of N Γ ⋆ ( x ) N_{\Gamma}^{\star}(x) N Γ ⋆ ( x ) .
Remark 5.8. By Lemma 5.6 , if Γ \Gamma Γ is an integral nonbipartite walk-regular graph, then we have two polynomials, N Γ ( x ) N_{\Gamma}(x) N Γ ( x ) and N Γ ⋆ ( x ) N_{\Gamma}^{\star}(x) N Γ ⋆ ( x ) , at our disposal to test sedentariness in Γ \Gamma Γ .
Corollary 5.9. Let Γ \Gamma Γ be an integral walk-regular graph. If gcd ( N Γ ( x ) , N Γ ⋆ ( x ) ) = 1 \gcd(N_{\Gamma}(x),N_{\Gamma}^{\star}(x))=1 g cd( N Γ ( x ) , N Γ ⋆ ( x )) = 1 , then Γ \Gamma Γ is sedentary.
Proof. We will prove the contrapositive. Suppose Γ \Gamma Γ is not sedentary. Then N Γ ( x ) N_{\Gamma}(x) N Γ ( x ) has a root λ \lambda λ on the unit circle by Theorem 5.7 . Since N Γ ( x ) N_{\Gamma}(x) N Γ ( x ) is a polynomial with integer coefficients, it follows that all its conjugates, including 1 / λ 1/\lambda 1/ λ , are also roots of N Γ ( x ) N_{\Gamma}(x) N Γ ( x ) . Since 1 / λ 1/\lambda 1/ λ is a root of N Γ ( x ) N_{\Gamma}(x) N Γ ( x ) , it follows that N Γ ( x ) N_{\Gamma}(x) N Γ ( x ) and N Γ ⋆ ( x ) N_{\Gamma}^{\star}(x) N Γ ⋆ ( x ) share a common non-constant factor.
Remark 5.10. The converse of Corollary 5.9 need not be true. We provide a counterexample in the family of unitary Cayley graphs introduced in [21 ] and generalized in [1 , 30 ] . Let R R R be a finite commutative ring. Let S S S be a subset of R R R such that S = − S S=-S S = − S . We say that Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) is a gcd-graph if S S S is stable under multiplication by units in R R R . When S = R × S=R^{\times} S = R × , the graph is called a unitary Cayley graph and we write G R = Γ ( R , R × ) G_R=\Gamma(R,R^{\times}) G R = Γ ( R , R × ) . Gcd-graphs possess elegant properties, such as the explicit description of their spectra via Ramanujan sums. In particular, it is known that they are integral graphs. These properties lie at the cross of algebra, number theory, and graph theory which makes it an ideal candidate for our investigation.
Let Γ = G 12 = Cay ( Z 12 , { 1 , 5 , 7 , 11 } ) \Gamma=G_{12}=\operatorname{Cay}(\mathbb{Z}_{12},\{1,5,7,11\}) Γ = G 12 = Cay ( Z 12 , { 1 , 5 , 7 , 11 }) (the unitary Cayley graph on Z 12 \mathbb{Z}_{12} Z 12 ). Then we have
N Γ ( x ) = x 8 + 2 x 6 + 6 x 4 + 2 x 2 + 1. N_{\Gamma}(x)=x^{8}+2x^{6}+6x^{4}+2x^{2}+1. N Γ ( x ) = x 8 + 2 x 6 + 6 x 4 + 2 x 2 + 1.
By the triangle inequality, one can verify that N Γ ( x ) N_{\Gamma}(x) N Γ ( x ) has no root on the unit circle, and so Γ \Gamma Γ is sedentary by Theorem 5.7 . This polynomial is reciprocal, so gcd ( N Γ ( x ) , N Γ ⋆ ( x ) ) ≠ 1 \gcd(N_{\Gamma}(x),N_{\Gamma}^{\star}(x))\ne1 g cd( N Γ ( x ) , N Γ ⋆ ( x )) = 1 .
An algebraic lemma
In this section, we describe some special cases where we can use tools from algebraic number theory to show that N Γ ( x ) N_{\Gamma}(x) N Γ ( x ) has no root on the unit circle.
Lemma 5.11. Let P ( x ) ∈ Z [ x ] P(x)\in\mathbb{Z}[x] P ( x ) ∈ Z [ x ] be a monic polynomial of degree m m m . Suppose that P ( x ) P(x) P ( x ) can be written as P ( x ) = x m + q Q ( x ) P(x)=x^{m}+qQ(x) P ( x ) = x m + q Q ( x ) where q ≥ 2 q\ge2 q ≥ 2 is a positive integer and Q ( x ) ∈ Z [ x ] Q(x)\in\mathbb{Z}[x] Q ( x ) ∈ Z [ x ] is a polynomial of degree less than m m m . Then, P ( x ) P(x) P ( x ) has no root on the unit circle.
We provide two proofs for Lemma 5.11 . They are based on the same idea. The first proof is shorter but the second proof could be used to give an explicit bound on sedentariness.
First proof. By way of contradiction, suppose θ ∈ C \theta\in\mathbb{C} θ ∈ C such that ∣ θ ∣ = 1 |\theta|=1 ∣ θ ∣ = 1 and P ( θ ) = 0 P(\theta)=0 P ( θ ) = 0 . Let F F F be the splitting field of P P P and O F \mathcal{O}_F O F be its ring of algebraic integers. By assumption, θ ∈ O F \theta\in\mathcal{O}_F θ ∈ O F . Since P ( x ) P(x) P ( x ) has real coefficients, θ ‾ \overline{\theta} θ is also a root of P ( x ) P(x) P ( x ) . Thus, θ ‾ ∈ O F \overline{\theta}\in\mathcal{O}_F θ ∈ O F . Since ∣ θ ∣ = 1 |\theta|=1 ∣ θ ∣ = 1 , have θ θ ˉ = 1 \theta\bar{\theta}=1 θ θ ˉ = 1 , and so θ \theta θ is a unit in O F \mathcal{O}_F O F . Now because θ m = − q Q ( θ ) \theta^m=-qQ(\theta) θ m = − q Q ( θ ) and θ \theta θ is a unit in O F \mathcal{O}_F O F , it follows that − q -q − q is a unit in O F \mathcal{O}_F O F . Since q ≥ 2 q\ge2 q ≥ 2 , this is a contradiction. □ \square □
Second proof. Let P ∗ ( x ) : = x m P ( 1 / x ) P^*(x):=x^mP(1/x) P ∗ ( x ) := x m P ( 1/ x ) be the reciprocal polynomial of P P P . We first claim that
gcd ( P , P ∗ ) = 1 \gcd(P,P^*)=1 g cd( P , P ∗ ) = 1
and the result will follow from the proof for Corollary 5.9. Suppose to the contrary that P P P and P ∗ P^* P ∗ have a nonconstant common factor, say F ( x ) ∈ Q [ x ] F(x)\in\mathbb{Q}[x] F ( x ) ∈ Q [ x ] . Since P P P is monic, by Gauss’s lemma on primitive polynomials, we may assume that F ( x ) F(x) F ( x ) is a monic polynomial in Z [ x ] \mathbb{Z}[x] Z [ x ] . Let us write P = F G 1 P=FG_1 P = F G 1 , P ∗ = F G 2 P^*=FG_2 P ∗ = F G 2 where G 1 , G 2 ∈ Z [ x ] G_1,G_2\in\mathbb{Z}[x] G 1 , G 2 ∈ Z [ x ] both have degree less than m m m . Let p p p be a prime divisor of q q q . Taking reduction modulo p p p , we have the following equalities in F p [ x ] \mathbb{F}_p[x] F p [ x ]
x m = F ˉ G ˉ 1 , 1 = F ˉ G ˉ 2 . x^m=\bar{F}\bar{G}_1,\quad1=\bar{F}\bar{G}_2. x m = F ˉ G ˉ 1 , 1 = F ˉ G ˉ 2 .
Since F F F is monic, the second equation implies that F ˉ \bar{F} F ˉ is a constant while the first equation implies that F ˉ = x k \bar{F}=x^k F ˉ = x k for some 1 ≤ k ≤ m 1\le k\le m 1 ≤ k ≤ m . This is a contradiction. □ \square □
Theorem 5.12. Let Γ \Gamma Γ be a connected, integral, walk-regular graph with valency d d d . If the multiplicity of each λ ∈ σ ( Γ ) ∖ { d } \lambda\in\sigma(\Gamma)\setminus\{d\} λ ∈ σ ( Γ ) ∖ { d } is a multiple of some integer q ≥ 2 q\ge2 q ≥ 2 , then Γ \Gamma Γ is sedentary.
Proof. By our assumption, N Γ ( x ) = x m + q Q ( x ) N_\Gamma(x)=x^m+qQ(x) N Γ ( x ) = x m + q Q ( x ) where deg ( Q ) < m \deg(Q)<m deg ( Q ) < m . By Lemma 5.11, we know that N Γ ( x ) N_\Gamma(x) N Γ ( x ) has no root on the unit circle. Thus, Γ \Gamma Γ is sedentary by Theorem 5.7. □ \square □
Corollary 5.13. Let Γ = K n 1 × ⋯ × K n r \Gamma=K_{n_1}\times\cdots\times K_{n_r} Γ = K n 1 × ⋯ × K n r . If gcd ( n 1 − 1 , … , n r − 1 ) > 1 \gcd(n_1-1,\ldots,n_r-1)>1 g cd( n 1 − 1 , … , n r − 1 ) > 1 , then Γ \Gamma Γ is sedentary. In particular, K n × k K_n^{\times k} K n × k is sedentary for all n ≥ 3 n\ge3 n ≥ 3 and k ≥ 1 k\ge1 k ≥ 1 .
Proof. The valency of Γ \Gamma Γ is given by d = ∏ i = 1 r ( n i − 1 ) d=\prod_{i=1}^{r}(n_i-1) d = ∏ i = 1 r ( n i − 1 ) . For a subset I ⊆ { 1 , … , r } I\subseteq\{1,\ldots,r\} I ⊆ { 1 , … , r } , we have that ( − 1 ) ∣ I ∣ ∏ i ∉ I ( n i − 1 ) (-1)^{|I|}\prod_{i\notin I}(n_i-1) ( − 1 ) ∣ I ∣ ∏ i ∈ / I ( n i − 1 ) is an eigenvalue of Γ \Gamma Γ with multiplicity ∏ i ∈ I ( n i − 1 ) \prod_{i\in I}(n_i-1) ∏ i ∈ I ( n i − 1 ) . Let q = gcd ( n 1 − 1 , … , n r − 1 ) > 1 q=\gcd(n_1-1,\ldots,n_r-1)>1 q = g cd( n 1 − 1 , … , n r − 1 ) > 1 . Then, every nonempty subset contributes a multiplicity divisible by q q q . Furthermore, if several subsets produce the same eigenvalue, their contributions are added. Consequently, every eigenvalue other than d d d has multiplicity divisible by q q q . We then see that Theorem 5.12 yields the result. □ \square □
Let Γ = K n 1 × ⋯ × K n r \Gamma=K_{n_1}\times\cdots\times K_{n_r} Γ = K n 1 × ⋯ × K n r where n j = 2 n_j=2 n j = 2 for some j j j . Then gcd ( n 1 − 1 , … , n r − 1 ) = 1 \gcd(n_1-1,\ldots,n_r-1)=1 g cd( n 1 − 1 , … , n r − 1 ) = 1 and so the conclusion in Corollary 5.13 does not apply. Nevertheless, since Γ \Gamma Γ in this case is a nonsingular bipartite graph, [22 ] , Theorem 12 implies that Γ \Gamma Γ is not sedentary.
Explicit bound for sedentariness
Theorem 5.12 implies that if the necklace polynomial of Γ \Gamma Γ has a certain form, then Γ \Gamma Γ is sedentary. In this section, we find an explicit constant C C C such that Γ \Gamma Γ is C C C -sedentary. To do this, we will use the theory of resultants.
Let f = a n x n + a n − 1 x n − 1 + ⋯ + a 0 ∈ C [ x ] f=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0\in\mathbb{C}[x] f = a n x n + a n − 1 x n − 1 + ⋯ + a 0 ∈ C [ x ] be a polynomial. The height of f f f is defined as
H ( f ) = max 0 ≤ i ≤ n ∣ a i ∣ . H(f)=\max_{0\le i\le n}|a_i|. H ( f ) = 0 ≤ i ≤ n max ∣ a i ∣.
Lemma 5.14. Let M ∈ M N ( C ) M\in M_N(\mathbb{C}) M ∈ M N ( C ) be an invertible matrix. Let x = ( x 1 , … , x N ) T ∈ C N \mathbf{x}=(x_1,\ldots,x_N)^{\mathsf{T}}\in\mathbb{C}^N x = ( x 1 , … , x N ) T ∈ C N be a solution to the equation M x = v M\mathbf{x}=\mathbf{v} M x = v , where v \mathbf{v} v is a unit vector. Let B B B be a positive number such that ∣ M i j ∣ ≤ B |M_{ij}|\le B ∣ M ij ∣ ≤ B for all 1 ≤ i , j ≤ N 1\le i,j\le N 1 ≤ i , j ≤ N . Then, for each 1 ≤ k ≤ N 1\le k\le N 1 ≤ k ≤ N , we have
∣ x k ∣ ≤ B N − 1 N ( N − 1 ) / 2 ∣ det ( M ) ∣ . |x_k|\le\frac{B^{N-1}N^{(N-1)/2}}{|\det(M)|}. ∣ x k ∣ ≤ ∣ det ( M ) ∣ B N − 1 N ( N − 1 ) /2 .
Furthermore, if M M M has integer coefficients, then ∣ x k ∣ ≤ B N − 1 N ( N − 1 ) / 2 |x_k| \le B^{N-1}N^{(N-1)/2} ∣ x k ∣ ≤ B N − 1 N ( N − 1 ) /2 for each 1 ≤ k ≤ N 1 \le k \le N 1 ≤ k ≤ N .
Proof. Let c 1 , … , c N \mathbf{c}_1,\ldots,\mathbf{c}_N c 1 , … , c N be the column vectors of M M M . By our assumption, ∥ c i ∥ ≤ B N \lVert\mathbf{c}_i\rVert\le B\sqrt{N} ∥ c i ∥ ≤ B N for each 1 ≤ i ≤ N 1 \le i \le N 1 ≤ i ≤ N . By Cramer’s rule, x k = det ( M k ) det ( M ) x_k = \frac{\det(M_k)}{\det(M)} x k = d e t ( M ) d e t ( M k ) where M k M_k M k is the matrix obtained by replacing the k k k -th column of M M M by v \mathbf{v} v . Applying Hadamard’s inequality, we have
∣ det ( M k ) ∣ ≤ ∥ v ∥ ⋅ ∏ j ≠ k ∥ c j ∥ ≤ B N − 1 N N − 1 2 . \lvert\det(M_k)\rvert\le\lVert\mathbf{v}\rVert\cdot\prod_{j\ne k}\lVert\mathbf{c}_j\rVert\le B^{N-1}N^{\frac{N-1}{2}}. ∣ det ( M k )∣ ≤ ∥ v ∥ ⋅ j = k ∏ ∥ c j ∥ ≤ B N − 1 N 2 N − 1 .
Therefore,
∣ x k ∣ ≤ B N − 1 N ( N − 1 ) / 2 ∣ det ( M ) ∣ . \lvert x_k\rvert\le\frac{B^{N-1}N^{(N-1)/2}}{\lvert\det(M)\rvert}. ∣ x k ∣ ≤ ∣ det ( M )∣ B N − 1 N ( N − 1 ) /2 .
If M M M has integer coefficients then ∣ det ( M ) ∣ ≥ 1 \lvert\det(M)\rvert\ge1 ∣ det ( M )∣ ≥ 1 and the inequality follows.
For polynomials f , g ∈ C [ x ] f,g \in\mathbb{C}[x] f , g ∈ C [ x ] , we let deg ( f ) \deg(f) deg ( f ) denote the degree of f f f and Res ( f , g ) \operatorname{Res}(f,g) Res ( f , g ) denote the resultant of f f f and g g g .
Proposition 5.15. Let f , g ∈ C [ x ] f,g \in\mathbb{C}[x] f , g ∈ C [ x ] be polynomials such that gcd ( f , g ) = 1 \gcd(f,g)=1 g cd( f , g ) = 1 . Let B ∈ R B \in\mathbb{R} B ∈ R such that B ≥ max { H ( f ) , H ( g ) } B \ge\max\{H(f),H(g)\} B ≥ max { H ( f ) , H ( g )} . Then, there exist p , q ∈ C [ x ] p,q \in\mathbb{C}[x] p , q ∈ C [ x ] such that:
p f + q g = 1 pf+qg=1 p f + q g = 1 .
deg ( p ) ≤ deg ( g ) − 1 \deg(p) \le\deg(g)-1 deg ( p ) ≤ deg ( g ) − 1 and deg ( q ) ≤ deg ( f ) − 1 \deg(q) \le\deg(f)-1 deg ( q ) ≤ deg ( f ) − 1 .
If N = deg ( f ) + deg ( g ) N=\deg(f)+\deg(g) N = deg ( f ) + deg ( g ) , then
H ( p ) , H ( q ) ≤ B N − 1 N ( N − 1 ) / 2 ∣ Res ( f , g ) ∣ . H(p),H(q) \le\frac{B^{N-1}N^{(N-1)/2}}{\lvert\operatorname{Res}(f,g)\rvert}. H ( p ) , H ( q ) ≤ ∣ Res ( f , g )∣ B N − 1 N ( N − 1 ) /2 . In particular, if f , g ∈ Z [ x ] f,g \in\mathbb{Z}[x] f , g ∈ Z [ x ] then we have H ( p ) , H ( q ) ≤ B N − 1 N ( N − 1 ) / 2 H(p),H(q) \le B^{N-1}N^{(N-1)/2} H ( p ) , H ( q ) ≤ B N − 1 N ( N − 1 ) /2 .
Proof. The coefficients of p , q p,q p , q are solutions of a linear system of the form S x = e N S\mathbf{x}=\mathbf{e}_N S x = e N where S S S is the Sylvester matrix of f f f and g g g , and e N \mathbf{e}_N e N is a standard vector. So the the existence of p , q p,q p , q , with the properties (1) and (2), follows from elimination theory, see [11 Proposition 9, Chapter 5] . Furthermore, by definition, Res ( f , g ) = det ( S ) \operatorname{Res}(f,g)=\det(S) Res ( f , g ) = det ( S ) , so the upper bound on H ( p ) H(p) H ( p ) and H ( q ) H(q) H ( q ) then follows from Lemma 5.14.
Remark 5.16. The bound in Proposition 5.15 is not optimal, since each column of S S S is obtained from the coefficients of f f f and g g g , and zeros. Thus, the bound on ∥ c ∥ \lVert\mathbf{c}\rVert ∥ c ∥ , where c \mathbf{c} c is a column of S S S , can be sharpened. However, for our purposes, the above bound is sufficient.
Lemma 5.17. Let B > 0 B>0 B > 0 and P n , B ⊂ Z [ x ] \mathcal{P}_{n,B}\subset\mathbb{Z}[x] P n , B ⊂ Z [ x ] be a set of polynomials such that for all P ∈ P n , B P\in\mathcal{P}_{n,B} P ∈ P n , B the following hold:
deg ( P ) = n \deg(P)=n deg ( P ) = n and H ( P ) ≤ B H(P)\le B H ( P ) ≤ B and P ( 0 ) ≠ 0 P(0)\ne0 P ( 0 ) = 0 ; and
gcd ( P , P ⋆ ) = 1 \gcd(P,P^\star)=1 g cd( P , P ⋆ ) = 1 , where P ⋆ ( x ) = x n P ( 1 / x ) P^\star(x)=x^nP(1/x) P ⋆ ( x ) = x n P ( 1/ x ) is the reciprocal polynomial of P P P .
Then there exists a constant C > 0 C>0 C > 0 , depending only on n n n and B B B , such that for all z ∈ C z\in\mathbb{C} z ∈ C with ∣ z ∣ = 1 \lvert z\rvert=1 ∣ z ∣ = 1 , we have ∣ P ( z ) ∣ ≥ C \lvert P(z)\rvert\ge C ∣ P ( z )∣ ≥ C for all P ∈ P n , B P\in\mathcal{P}_{n,B} P ∈ P n , B . In fact, we may choose C = 1 B 2 n − 1 ( 2 n ) ( 2 n + 1 ) / 2 C=\frac{1}{B^{2n-1}(2n)^{(2n+1)/2}} C = B 2 n − 1 ( 2 n ) ( 2 n + 1 ) /2 1 .
Proof. Let P ∈ P n , B P\in\mathcal{P}_{n,B} P ∈ P n , B . Since gcd ( P , P ⋆ ) = 1 \gcd(P,P^\star)=1 g cd( P , P ⋆ ) = 1 , by Proposition 5.15 , we can find p , q p,q p , q such that deg ( p ) , deg ( q ) ≤ n − 1 \deg(p),\deg(q)\le n-1 deg ( p ) , deg ( q ) ≤ n − 1 such that p P + q P ⋆ = 1 pP+qP^\star=1 pP + q P ⋆ = 1 and H ( p ) , H ( q ) ≤ B 2 n − 1 ( 2 n ) ( 2 n − 1 ) / 2 H(p),H(q)\le B^{2n-1}(2n)^{(2n-1)/2} H ( p ) , H ( q ) ≤ B 2 n − 1 ( 2 n ) ( 2 n − 1 ) /2 . Let z ∈ C z \in\mathbb{C} z ∈ C with ∣ z ∣ = 1 |z|=1 ∣ z ∣ = 1 . Since P P P has real coefficients, P ( 1 / z ) = P ( z ‾ ) = P ( z ) ‾ P(1/z)=P(\overline{z})=\overline{P(z)} P ( 1/ z ) = P ( z ) = P ( z ) . Thus, ∣ P ⋆ ( z ) ∣ = ∣ z n P ( 1 / z ) ∣ = ∣ P ( z ) ∣ |P^{\star}(z)|=|z^{n}P(1/z)|=|P(z)| ∣ P ⋆ ( z ) ∣ = ∣ z n P ( 1/ z ) ∣ = ∣ P ( z ) ∣ . By the triangle inequality, ∣ p ( z ) ∣ ≤ n H ( p ) ≤ n B 2 n − 1 ( 2 n ) ( 2 n − 1 ) / 2 |p(z)|\le nH(p)\le nB^{2n-1}(2n)^{(2n-1)/2} ∣ p ( z ) ∣ ≤ n H ( p ) ≤ n B 2 n − 1 ( 2 n ) ( 2 n − 1 ) /2 .
Similarly, ∣ q ( z ) ∣ ≤ n H ( q ) ≤ n B 2 n − 1 ( 2 n ) ( 2 n − 1 ) / 2 |q(z)|\le nH(q)\le nB^{2n-1}(2n)^{(2n-1)/2} ∣ q ( z ) ∣ ≤ n H ( q ) ≤ n B 2 n − 1 ( 2 n ) ( 2 n − 1 ) /2 . Since 1 = P ( z ) p ( z ) + P ⋆ ( z ) q ( z ) 1=P(z)p(z)+P^{\star}(z)q(z) 1 = P ( z ) p ( z ) + P ⋆ ( z ) q ( z ) , we get
1 ≤ ∣ P ( z ) ∣ ∣ p ( z ) ∣ + ∣ P ⋆ ( z ) ∣ ∣ q ( z ) ∣ = ∣ P ( z ) ∣ ( ∣ p ( z ) ∣ + ∣ q ( z ) ∣ ) . 1\le|P(z)||p(z)|+|P^{\star}(z)||q(z)|=|P(z)|(|p(z)|+|q(z)|). 1 ≤ ∣ P ( z ) ∣∣ p ( z ) ∣ + ∣ P ⋆ ( z ) ∣∣ q ( z ) ∣ = ∣ P ( z ) ∣ ( ∣ p ( z ) ∣ + ∣ q ( z ) ∣ ) .
by the triangle inequality. Consequently, we have
∣ P ( z ) ∣ ≥ 1 ∣ p ( z ) ∣ + ∣ q ( z ) ∣ ≥ 1 2 n B 2 n − 1 ( 2 n ) ( 2 n − 1 ) / 2 = 1 B 2 n − 1 ( 2 n ) ( 2 n + 1 ) / 2 . |P(z)|\ge\frac{1}{|p(z)|+|q(z)|}\ge\frac{1}{2nB^{2n-1}(2n)^{(2n-1)/2}}=\frac{1}{B^{2n-1}(2n)^{(2n+1)/2}}. ∣ P ( z ) ∣ ≥ ∣ p ( z ) ∣ + ∣ q ( z ) ∣ 1 ≥ 2 n B 2 n − 1 ( 2 n ) ( 2 n − 1 ) /2 1 = B 2 n − 1 ( 2 n ) ( 2 n + 1 ) /2 1 .
We are now ready to prove the main result in this subsection.
Theorem 5.18. Let Γ \Gamma Γ be an integral walk-regular graph on n n n vertices such that N Γ ( x ) N_{\Gamma}(x) N Γ ( x ) has the form x m + q Q ( x ) x^{m}+qQ(x) x m + q Q ( x ) for some integer q ≥ 2 q\ge2 q ≥ 2 and polynomial Q ( x ) ∈ Z [ x ] Q(x)\in\mathbb{Z}[x] Q ( x ) ∈ Z [ x ] such that deg ( Q ) < m \deg(Q)<m deg ( Q ) < m . Then Γ \Gamma Γ is C C C -sedentary with C = 1 n 2 n ( 2 n ) ( 2 n + 1 ) / 2 C=\frac{1}{n^{2n}(2n)^{(2n+1)/2}} C = n 2 n ( 2 n ) ( 2 n + 1 ) /2 1 .
Proof. As deg ( Q ( x ) ) < m \deg(Q(x))<m deg ( Q ( x )) < m , we have deg ( N Γ ) = m \deg(N_{\Gamma})=m deg ( N Γ ) = m and we may choose m = λ 1 − λ n m=\lambda_{1}-\lambda_{n} m = λ 1 − λ n . By [16 Proposition 1.2] , m ≤ n m\le n m ≤ n . We know that gcd ( N Γ ( x ) , N Γ ⋆ ( x ) ) = 1 \gcd(N_{\Gamma}(x),N_{\Gamma}^{\star}(x))=1 g cd( N Γ ( x ) , N Γ ⋆ ( x )) = 1 by the second proof of Lemma 5.11. Since the multiplicity of each eigenvalue of Γ \Gamma Γ is bounded above by n n n , we also know that H ( N Γ ) ≤ n H(N_{\Gamma})\le n H ( N Γ ) ≤ n . Thus, for all t ∈ R t\in\mathbb{R} t ∈ R and for every vertex u u u of Γ \Gamma Γ , Lemma 5.17 yields
∣ U ( t ) u , u ∣ = 1 n ∣ N Γ ( z ) ∣ ≥ 1 n ⋅ 1 n 2 m − 1 ( 2 m ) ( 2 m + 1 ) / 2 = 1 n 2 m ( 2 m ) ( 2 m + 1 ) / 2 ≥ 1 n 2 n ( 2 n ) ( 2 n + 1 ) / 2 . |U(t)_{u,u}|=\frac{1}{n}|N_{\Gamma}(z)|\ge\frac{1}{n}\cdot\frac{1}{n^{2m-1}(2m)^{(2m+1)/2}}=\frac{1}{n^{2m}(2m)^{(2m+1)/2}}\ge\frac{1}{n^{2n}(2n)^{(2n+1)/2}}. ∣ U ( t ) u , u ∣ = n 1 ∣ N Γ ( z ) ∣ ≥ n 1 ⋅ n 2 m − 1 ( 2 m ) ( 2 m + 1 ) /2 1 = n 2 m ( 2 m ) ( 2 m + 1 ) /2 1 ≥ n 2 n ( 2 n ) ( 2 n + 1 ) /2 1 .
Cayley graphs
We now apply our results to Cayley graphs. In particular, our main goal in this section is to show that an integral Cayley graph on a group of odd order is sedentary.
Spectra of Cayley graphs
Let G G G be a finite group and S ⊂ G S\subset G S ⊂ G . The Cayley graph Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) has vertex set G G G and g , h ∈ G g,h\in G g , h ∈ G are adjacent if and only if g − 1 h ∈ S g^{-1}h\in S g − 1 h ∈ S . Throughout, we assume S S S is a nonempty inverse-closed subset and 1 ∉ S 1\notin S 1 ∈ / S , so that Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is a simple undirected graph with at least one edge. Note that Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is connected if and only if S S S generates G G G . Let ρ : G → G L n ( C ) \rho:G\to GL_{n}(\mathbb{C}) ρ : G → G L n ( C ) be an irreducible unitary representation of G G G of degree n = d ρ = dim ( ρ ) n=d_{\rho}=\dim(\rho) n = d ρ = dim ( ρ ) . Then ρ \rho ρ extends to a ring map ρ : C [ G ] → M n ( C ) \rho:\mathbb{C}[G]\to M_{n}(\mathbb{C}) ρ : C [ G ] → M n ( C ) . For S ⊂ G S\subset G S ⊂ G , define
ρ S : = ∑ s ∈ S ρ ( s ) . \rho_{S}:=\sum_{s\in S}\rho(s). ρ S := s ∈ S ∑ ρ ( s ) .
We have the following theorem about the spectrum of a Cayley graph.
Theorem 6.1. [12 Theorem 3] The eigenvalues of a Cayley graph Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) are the union of the multisets of eigenvalues of ρ S \rho_{S} ρ S , each repeated d ρ d_{\rho} d ρ times, where ρ \rho ρ runs over one representative from each equivalence class of irreducible unitary representations of G G G . Further, if the multiplicity of λ \lambda λ as an eigenvalue of ρ S \rho_{S} ρ S is m ( λ , ρ ) m(\lambda,\rho) m ( λ , ρ ) , then its multiplicity as an eigenvalue of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is equal to ∑ ρ d ρ m ( λ , ρ ) \sum_{\rho}d_{\rho}m(\lambda,\rho) ∑ ρ d ρ m ( λ , ρ ) .
We let ρ 0 \rho_{0} ρ 0 be the trivial representation of G G G . Note that ρ 0 S = ∣ S ∣ \rho_{0S}=|S| ρ 0 S = ∣ S ∣ is the valency of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) .
Theorem 6.2. Let Γ = Γ ( G , S ) \Gamma=\Gamma(G,S) Γ = Γ ( G , S ) be a Cayley graph, where G G G is a finite group of odd order. Then the multiplicity of each λ ∈ σ ( Γ ) ∖ { ρ 0 S } \lambda\in\sigma(\Gamma)\setminus\{\rho_{0S}\} λ ∈ σ ( Γ ) ∖ { ρ 0 S } is an even number while that of ρ 0 S \rho_{0S} ρ 0 S is odd.
Proof. Let G ′ G' G ′ be the group generated by S S S . Then Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is a disjoint union of [ G : G ′ ] [G:G'] [ G : G ′ ] copies of Γ ( G ′ , S ) \Gamma(G',S) Γ ( G ′ , S ) . As [ G : G ′ ] [G:G'] [ G : G ′ ] is odd, it suffices to prove the result for the connected graph Γ ( G ′ , S ) \Gamma(G',S) Γ ( G ′ , S ) .
Suppose Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is connected so that ρ 0 S \rho_{0S} ρ 0 S has multiplicity one. Let λ \lambda λ be another eigenvalue of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) so that λ < ρ 0 S \lambda< \rho_{0S} λ < ρ 0 S . By Theorem 6.1 , λ \lambda λ is an eigenvalue of ρ S \rho_S ρ S where ρ : G → GL n ( C ) \rho:G\to\operatorname{GL}_n(\mathbb{C}) ρ : G → GL n ( C ) is a non-trivial irreducible unitary representation of G G G . Let ρ ˉ \bar{\rho} ρ ˉ be the conjugate representation of ρ \rho ρ ; namely ρ ˉ : G → GL n ( C ) \bar{\rho}:G\to\operatorname{GL}_n(\mathbb{C}) ρ ˉ : G → GL n ( C ) is defined by ρ ˉ ( g ) = ρ ( g ) ‾ \bar{\rho}(g)=\overline{\rho(g)} ρ ˉ ( g ) = ρ ( g ) . Since ρ \rho ρ is unitary, ρ ( s − 1 ) = ρ ( s ) − 1 = ρ ( s ) ∗ = ρ ( s ) ‾ T \rho(s^{-1})=\rho(s)^{-1}=\rho(s)^{*}=\overline{\rho(s)}^{T} ρ ( s − 1 ) = ρ ( s ) − 1 = ρ ( s ) ∗ = ρ ( s ) T . Therefore, ρ ˉ ( s − 1 ) = ρ ( s ) T \bar{\rho}(s^{-1})=\rho(s)^{T} ρ ˉ ( s − 1 ) = ρ ( s ) T . Since ∣ G ∣ |G| ∣ G ∣ is odd, ρ ≠ ρ ˉ \rho\ne\bar{\rho} ρ = ρ ˉ by the Frobenius-Schur index theorem, see [34 Proposition 39] . Using the fact that S = S − 1 S=S^{-1} S = S − 1 , we have
ρ ˉ S = ∑ s ∈ S ρ ˉ ( s ) = ∑ s ∈ S ρ ˉ ( s − 1 ) = ∑ s ∈ S ρ ( s ) T = ρ S T . \bar{\rho}_S=\sum_{s\in S}\bar{\rho}(s)=\sum_{s\in S}\bar{\rho}(s^{-1})=\sum_{s\in S}\rho(s)^T=\rho_S^T. ρ ˉ S = s ∈ S ∑ ρ ˉ ( s ) = s ∈ S ∑ ρ ˉ ( s − 1 ) = s ∈ S ∑ ρ ( s ) T = ρ S T .
Now, because ρ S \rho_S ρ S and ρ S T \rho_S^T ρ S T have the same characteristic polynomial, this shows that λ \lambda λ also appears in ρ ˉ S \bar{\rho}_S ρ ˉ S . Since ρ ≠ ρ ˉ \rho\ne\bar{\rho} ρ = ρ ˉ and ρ S \rho_S ρ S and ρ ˉ S \bar{\rho}_S ρ ˉ S have the same characteristic polynomial, the non-trivial irreducible representations occur in distinct conjugate pairs contributing the same multiplicity of λ \lambda λ . Hence the total multiplicity of λ \lambda λ is even. □
Since a Cayley graph is necessarily walk-regular, we obtain our main result in this section.
Theorem 6.3. Let G G G be a finite group of odd order. If Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is integral, then it is sedentary.
Proof. Let G ′ = ⟨ S ⟩ G'=\langle S\rangle G ′ = ⟨ S ⟩ . Then Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is a disjoint union of [ G : G ′ ] [G:G'] [ G : G ′ ] copies of the connected Cayley graph Γ ( G ′ , S ) \Gamma(G',S) Γ ( G ′ , S ) . Since G ′ G' G ′ has odd order, Theorem 6.2 implies that every eigenvalue of Γ ( G ′ , S ) \Gamma(G',S) Γ ( G ′ , S ) other than the degree has even multiplicity. So by Theorem 5.12 , Γ ( G ′ , S ) \Gamma(G',S) Γ ( G ′ , S ) is sedentary. Thus, every connected component of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is sedentary, and so is Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) . □
Remark 6.4. Later, we will show that if G G G is a finite group of even order, then we can always find S S S such that Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is not sedentary (see Corollary 7.15).
Sedentariness in gcd-graphs
In this subsection, we study sedentariness of graphs defined over a finite ring R R R of characteristic n n n . In this case, the underlying vertex set is ( R , + ) (R,+) ( R , + ) . As observed in various previous works (see [21 , 30 , 35 ] ) what makes working with graphs defined over R R R more interesting is the interplay between the multiplicative structure and the additive structure of R R R . In particular, we have a quite elegant theory for rings in which R ^ \widehat{R} R is canonically isomorphic to R R R (see [17 , 31 ] ).
Definition 6.5. A finite ring R R R of characteristic n n n is called a symmetric Frobenius ring if there exists a generating character χ : ( R , + ) → C × \chi:(R,+)\to\mathbb{C}^{\times} χ : ( R , + ) → C × satisfying (i) χ \chi χ is symmetric; namely χ ( a b ) = χ ( b a ) \chi(ab)=\chi(ba) χ ( ab ) = χ ( ba ) for all a , b ∈ R a,b\in R a , b ∈ R ; and (ii) the map R → R ^ = Hom ( R , C × ) R\to\widehat{R}=\operatorname{Hom}(R,\mathbb{C}^{\times}) R → R = Hom ( R , C × ) given by r ↦ χ r r\mapsto\chi_r r ↦ χ r , where χ r ( a ) = χ ( r a ) \chi_r(a)=\chi(ra) χ r ( a ) = χ ( r a ) , is an isomorphism.
Examples of symmetric Frobenius rings include finite quotients of a Dedekind domain, finite fields, matrix rings, finite chain rings, and their products (see [17 , 28 ] ).
Let Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) be a Cayley graph where the underlying vertex set is ( R , + ) (R,+) ( R , + ) . When R R R is a finite symmetric Frobenius ring, the spectrum of Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) is canonically parametrized by R R R . More precisely, the spectrum of Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) is the multiset { λ r } r ∈ R \{\lambda_r\}_{r\in R} { λ r } r ∈ R where
λ r = ∑ s ∈ S χ r ( s ) = ∑ s ∈ S χ ( r s ) . \lambda_r=\sum_{s\in S}\chi_r(s)=\sum_{s\in S}\chi(rs). λ r = s ∈ S ∑ χ r ( s ) = s ∈ S ∑ χ ( r s ) .
We will use this explicit description to find instances where the conditions of Theorem 5.12 apply. To do so, we recall the following definition which was introduced in [31 ] .
Definition 6.6. Let U U U be a subgroup of R × R^{\times} R × . A Cayley graph Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) is U U U -unitary if S S S is stable under the left and right actions of U U U , i.e. U S U = S USU=S U S U = S . If Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) is U U U -unitary and U = R × U=R^{\times} U = R × , then Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) is called a gcd-graph.
Since R R R is a finite Z n \mathbb{Z}_n Z n -algebra, there is an induced group homomorphism ( Z n ) × → R × (\mathbb{Z}_n)^{\times}\to R^{\times} ( Z n ) × → R × . In what follows, we will identify ( Z n ) × (\mathbb{Z}_n)^{\times} ( Z n ) × with its image in R R R . It is known that the Cayley graph Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) is integral if and only if Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) is ( Z n ) × (\mathbb{Z}_n)^{\times} ( Z n ) × -unitary; namely S S S is stable under the multiplication by elements of ( Z n ) × (\mathbb{Z}_n)^{\times} ( Z n ) × (see [15 , 29 ] ).
Lemma 6.7. Let Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) be a U U U -unitary Cayley graph. If a = u b v a=ubv a = u b v for some u , v ∈ U u,v\in U u , v ∈ U , then λ a = λ b \lambda_a=\lambda_b λ a = λ b .
Proof. We have
λ a = ∑ s ∈ S χ a ( s ) = ∑ s ∈ S χ ( a s ) = ∑ s ∈ S χ ( u b v s ) = ∑ s ∈ S χ ( b v s u ) = ∑ t ∈ v S u χ ( b t ) = λ b . \lambda_a=\sum_{s\in S}\chi_a(s)=\sum_{s\in S}\chi(as)=\sum_{s\in S}\chi(ubvs)=\sum_{s\in S}\chi(bvsu)=\sum_{t\in vSu}\chi(bt)=\lambda_b. λ a = s ∈ S ∑ χ a ( s ) = s ∈ S ∑ χ ( a s ) = s ∈ S ∑ χ ( u b v s ) = s ∈ S ∑ χ ( b v s u ) = t ∈ v S u ∑ χ ( b t ) = λ b . Here, the last equality follows from the fact that v S u = S vSu=S v S u = S . □
In particular, the eigenvalue λ a \lambda_a λ a is equal for every a a a belonging to a U U U -double orbit in R R R , so the multiplicity of any nontrivial eigenvalue is a sum of the cardinalities of such orbits. Combining Theorem 5.12 and Lemma 6.7 , we have the following result.
Proposition 6.8. Let R R R be a finite symmetric Frobenius ring and Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) be a connected integral U U U -unitary Cayley graph where U ≤ R × U\le R^{\times} U ≤ R × . Suppose q ≥ 2 q\ge2 q ≥ 2 is an integer such that the cardinality of every double orbit U a U UaU U a U with a ≠ 0 a\ne0 a = 0 is divisible by q q q . Then Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) is sedentary.
We now discuss a few cases where we can apply Lemma 6.7 and Theorem 5.12 .
Proposition 6.9. Let q = p f ≥ 3 q=p^f\ge3 q = p f ≥ 3 be a prime power and R R R be a finite symmetric Frobenius F q \mathbb{F}_q F q -algebra. If Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) is a connected F q × \mathbb{F}_q^{\times} F q × -unitary Cayley graph, then the following hold.
Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) is integral.
The order of every orbit in F q × \ R ∗ / F q × \mathbb{F}_q^{\times}\backslash R^*/\mathbb{F}_q^{\times} F q × \ R ∗ / F q × is exactly q − 1 q-1 q − 1 . Here R ∗ = R ∖ { 0 } R^*=R\setminus\{0\} R ∗ = R ∖ { 0 } .
Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) is sedentary.
Proof. Since S S S is stable under the action of F q × \mathbb{F}_q^{\times} F q × , it is also stable under the action of F p × \mathbb{F}_p^{\times} F p × since F p × ⊂ F q × \mathbb{F}_p^{\times}\subset\mathbb{F}_q^{\times} F p × ⊂ F q × . The integrality of Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) follows from (1) follows from [28 Theorem 1.1] . Meanwhile, (2) follows from the fact that the orbit of an element a ∈ R ∗ a\in R^* a ∈ R ∗ in the double-quotient F q × \ R ∗ / F q × \mathbb{F}_q^{\times}\backslash R^*/\mathbb{F}_q^{\times} F q × \ R ∗ / F q × is precisely { c a ∣ c ∈ F q × } \{ca\mid c\in\mathbb{F}_q^{\times}\} { c a ∣ c ∈ F q × } (since F q \mathbb{F}_q F q is in the center of R R R , we only need to consider one-sided action). Finally, (3) follows from (1), (2) and Theorem 5.12 . □
Example 6.10. Let R = M 2 ( F 4 ) R=M_2(\mathbb{F}_4) R = M 2 ( F 4 ) and Γ : = Γ ( M 2 ( F 4 ) , GL 2 ( F 4 ) ) \Gamma:=\Gamma(M_2(\mathbb{F}_4),\operatorname{GL}_2(\mathbb{F}_4)) Γ := Γ ( M 2 ( F 4 ) , GL 2 ( F 4 )) be a unitary Cayley graph. The characteristic polynomial of Γ \Gamma Γ is ( x − 180 ) ( x + 12 ) 75 ( x − 4 ) 180 (x-180)(x+12)^{75}(x-4)^{180} ( x − 180 ) ( x + 12 ) 75 ( x − 4 ) 180 . The eigenvalues − 12 -12 − 12 and 4 4 4 have multiplicity divisible by 3 = 4 − 1 3=4-1 3 = 4 − 1 as predicted by Proposition 6.9 . We conclude that the unitary Cayley graph over R R R is sedentary.
Here is another situation where we can apply Theorem 5.12 .
Proposition 6.11. Let R R R be a finite commutative Frobenius ring; namely R = ∏ i = 1 d R i R=\prod_{i=1}^{d}R_i R = ∏ i = 1 d R i where each R i R_i R i is a local commutative Frobenius ring. Let κ i \kappa_i κ i be the size of the residue field of R i R_i R i . Suppose there is an integer q ≥ 2 q\ge2 q ≥ 2 such that κ i ≡ 1 ( m o d q ) \kappa_i\equiv1\pmod{q} κ i ≡ 1 ( mod q ) for each 1 ≤ i ≤ d 1\le i\le d 1 ≤ i ≤ d . If Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) is a connected R × R^\times R × -unitary Cayley graph, then the following statements hold.
Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) is integral.
The order of every orbit in R × \ R ∗ / R × R^\times\backslash R^*/R^\times R × \ R ∗ / R × is divisible by q q q . Here R ∗ = R ∖ { 0 } R^*=R\setminus\{0\} R ∗ = R ∖ { 0 } .
Γ ( R , S ) \Gamma(R,S) Γ ( R , S ) is sedentary.
Proof. Note that (1) is clear, while (3) follows from (1) and (2). So we only need to prove (2). By [30 Corollary 2.7] , we know that for each a ∈ R ∗ a\in R^* a ∈ R ∗ , the orbit containing a a a is precisely ( R / Ann R ( a ) ) × (R/\operatorname{Ann}_R(a))^\times ( R / Ann R ( a ) ) × where Ann R ( a ) = { x ∈ R ∣ a x = 0 } \operatorname{Ann}_R(a)=\{x\in R\mid ax=0\} Ann R ( a ) = { x ∈ R ∣ a x = 0 } . Since a ≠ 0 a\ne0 a = 0 , Ann R ( a ) \operatorname{Ann}_R(a) Ann R ( a ) is a proper ideal of R R R ; namely, it has the form ∏ i = 1 d I i \prod_{i=1}^{d}I_i ∏ i = 1 d I i where I i I_i I i is an ideal in R i R_i R i and there exists an index k k k such that I k ≠ R k I_k\ne R_k I k = R k . In this case, ∣ ( R / Ann R ( a ) ) × ∣ \lvert(R/\operatorname{Ann}_R(a))^\times\rvert ∣( R / Ann R ( a ) ) × ∣ is a multiple of ∣ ( R k / I k ) × ∣ \lvert(R_k/I_k)^\times\rvert ∣( R k / I k ) × ∣ . By definition, the residue field of R k / I k R_k/I_k R k / I k is also the residue field of R k R_k R k . Therefore ∣ ( R k / I k ) × ∣ \lvert(R_k/I_k)^\times\rvert ∣( R k / I k ) × ∣ is a multiple of κ k − 1 \kappa_k-1 κ k − 1 and hence a multiple of q q q . Thus ∣ ( R / Ann R ( a ) ) × ∣ \lvert(R/\operatorname{Ann}_R(a))^\times\rvert ∣( R / Ann R ( a ) ) × ∣ is a multiple of q q q for each a ∈ R ∗ a\in R^* a ∈ R ∗ .
Example 6.12. Let n = p q n=pq n = pq where p , q ≡ 1 ( m o d 3 ) p,q\equiv1\pmod{3} p , q ≡ 1 ( mod 3 ) are distinct primes and let S = { a ∈ Z n ∣ gcd ( a , n ) ∈ { p , q } } S=\{a\in\mathbb{Z}_n\mid\gcd(a,n)\in\{p,q\}\} S = { a ∈ Z n ∣ g cd( a , n ) ∈ { p , q }} . The characteristic polynomial of the gcd-graph Γ ( Z n , S ) ≅ K p □ K q \Gamma(\mathbb{Z}_n,S)\cong K_p\square K_q Γ ( Z n , S ) ≅ K p □ K q is given by ( x − ( p + q − 2 ) ) ( x − ( p − 2 ) ) q − 1 ( x − ( q − 2 ) ) p − 1 ( x + 2 ) ( p − 1 ) ( q − 1 ) (x-(p+q-2))(x-(p-2))^{q-1}(x-(q-2))^{p-1}(x+2)^{(p-1)(q-1)} ( x − ( p + q − 2 )) ( x − ( p − 2 ) ) q − 1 ( x − ( q − 2 ) ) p − 1 ( x + 2 ) ( p − 1 ) ( q − 1 ) . We see that all eigenvalues except p + q − 2 p+q-2 p + q − 2 have multiplicity divisible by 3 3 3 . More generally, if n = ∏ i = 1 r p i a i n=\prod_{i=1}^{r}p_i^{a_i} n = ∏ i = 1 r p i a i where p i p_i p i is a prime such that p i ≡ 1 ( m o d 3 ) p_i\equiv1\pmod{3} p i ≡ 1 ( mod 3 ) . Then any gcd-graph over Z n \mathbb{Z}_n Z n will be sedentary.
Twins in Cayley graphs
Our goal in this section is twofold. First, we characterize the existence of twins in Cayley graphs and vertex-transitive graphs, and second, we use this characterization to completely determine sedentariness in vertex-transitive graphs with twins. Throughout this section, G G G denotes a finite group.
Structure theorem
A subset X ⊆ V ( Γ ) X\subseteq V(\Gamma) X ⊆ V ( Γ ) is a homogeneous set if every vertex in V ( Γ ) ∖ X V(\Gamma)\setminus X V ( Γ ) ∖ X is adjacent to either all or none of the vertices in X X X [7 Definition 2.11] . Thus, X X X is a true (resp., false) twin set if and only if X X X is a maximal homogeneous set in Γ \Gamma Γ and the subgraph induced by X X X is complete (resp., empty). In [7 Theorem 3.4] , the authors provide a characterization of Cayley graphs that possess non-trivial homogeneous sets. In this section, we study the same problem for the existence of a twin set, which is somewhat easier since a twin set is necessarily a homogeneous set. Since X X X is a true twin set in Γ \Gamma Γ if and only if X X X is a false twin set in Γ ‾ \overline{\Gamma} Γ , it is sufficient to focus on true twin sets in Γ \Gamma Γ . The following fact is known.
Lemma 7.1. For each g ∈ G g\in G g ∈ G , the left multiplication map ℓ g : Γ ( G , S ) → Γ ( G , S ) \ell_g:\Gamma(G,S)\to\Gamma(G,S) ℓ g : Γ ( G , S ) → Γ ( G , S ) defined by x ↦ g x x\mapsto gx x ↦ g x is a graph automorphism.
We are now ready to prove one of the main results about twins in Cayley graphs.
Proposition 7.2. If X X X is a true twin set in Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) and 1 ∈ X 1\in X 1 ∈ X , then X X X is a subgroup of G G G . The same is true if X X X is a false twin set.
Proof. Let h ∈ X h \in X h ∈ X . By Lemmas 3.2 and 7.1 , h X hX h X is a twin set. Since 1 ∈ X 1 \in X 1 ∈ X , we get that h ∈ h X ∩ X h \in hX \cap X h ∈ h X ∩ X , and so all elements in h X ∪ X hX \cup X h X ∪ X are pairwise true twins by Lemma 3.1 . By the maximality of X X X and h X hX h X , we have h X = X hX = X h X = X . Thus X X X is closed under multiplication. Now, let h ∈ X h \in X h ∈ X . Then, there exists n > 0 n > 0 n > 0 such that h n = 1 h^n = 1 h n = 1 . Therefore, h − 1 = h n − 1 ∈ X h^{-1} = h^{n-1} \in X h − 1 = h n − 1 ∈ X , and so X X X is closed under inverses. This shows that X X X is a subgroup of G G G .
Lemma 7.3. Let H H H be a subgroup of G G G and Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) be a Cayley graph. Let S ∗ = S ∪ { 1 } S^* = S \cup\{1\} S ∗ = S ∪ { 1 } . Let g 1 H , … , g r H g_1H,\ldots,g_rH g 1 H , … , g r H be the set of all left cosets of H H H in G G G . The following are equivalent.
Pairwise, elements of H H H are true twins.
S ∗ S^* S ∗ is a union of cosets of H H H in G G G and H ⊂ S ∗ H \subset S^* H ⊂ S ∗ .
Moreover, if either of the above conditions holds, then Γ ( G , S ) ≅ Γ 1 [ K m ] \Gamma(G,S) \cong\Gamma_1[K_m] Γ ( G , S ) ≅ Γ 1 [ K m ] where m = ∣ H ∣ m = |H| m = ∣ H ∣ and the vertices of Γ 1 \Gamma_1 Γ 1 are the left cosets of H H H , and g i H g_iH g i H and g j H g_jH g j H are adjacent if and only if g i − 1 g j ∈ S g_i^{-1}g_j \in S g i − 1 g j ∈ S (this is independent of the choice of g i g_i g i for each coset as explained in Remark 7.4).
Proof. Assume every pair of elements in H H H are twins. Since the subgraph induced by H H H is complete, ( 1 , h ) ∈ E ( Γ ) (1,h) \in E(\Gamma) ( 1 , h ) ∈ E ( Γ ) for all h ∈ H ∖ { 1 } h \in H \setminus\{1\} h ∈ H ∖ { 1 } . Since h ∈ S h \in S h ∈ S by definition, we get H ⊂ S ∗ H \subset S^* H ⊂ S ∗ . Next, we claim that if g ∈ S g \in S g ∈ S , then g H ⊂ S ∗ gH \subset S^* g H ⊂ S ∗ . If g ∈ H g \in H g ∈ H , then we are done, so suppose that g ∉ H g \notin H g ∈ / H . Since S S S is closed under inversion, g − 1 ∈ S g^{-1} \in S g − 1 ∈ S which implies ( g − 1 , 1 ) ∈ E ( Γ ) (g^{-1},1) \in E(\Gamma) ( g − 1 , 1 ) ∈ E ( Γ ) . From the fact that H H H is a twin set, we know that ( g − 1 , h ) ∈ E ( Γ ) (g^{-1},h) \in E(\Gamma) ( g − 1 , h ) ∈ E ( Γ ) for all h ∈ H h \in H h ∈ H . Therefore, g h ∈ S gh \in S g h ∈ S for all h ∈ H h \in H h ∈ H . In other words g H ⊂ S ⊂ S ∗ gH \subset S \subset S^* g H ⊂ S ⊂ S ∗ .
Conversely, suppose that H ⊂ S ∗ H \subset S^* H ⊂ S ∗ and S ∗ S^* S ∗ is a union of left cosets of H H H in G G G . We claim that the elements of H H H are twins. First, we remark that since H ⊂ S ∗ H \subset S^* H ⊂ S ∗ , the induced subgraph on H H H is the complete graph. Next, we show that H H H is a homogeneous set. In fact, let g ∈ G ∖ H g \in G \setminus H g ∈ G ∖ H . Then ( g , h ) ∈ E ( Γ ) (g,h) \in E(\Gamma) ( g , h ) ∈ E ( Γ ) for some h ∈ H h \in H h ∈ H if and only if g − 1 h ∈ S g^{-1}h \in S g − 1 h ∈ S . Since S ∗ S^* S ∗ is a union of left-cosets, we know this happens if and only if g − 1 H ⊂ S g^{-1}H \subset S g − 1 H ⊂ S , which implies g g g is adjacent to every element in H H H . Thus, H H H is a homogeneous set in Γ \Gamma Γ .
The last statement follows from the fact that each coset g i H g_iH g i H is a set of twins in Γ \Gamma Γ .
Remark 7.4. Suppose S ∗ = S ∪ { 1 } S^* = S \cup\{1\} S ∗ = S ∪ { 1 } is a union of left cosets of H H H . Then S ∗ S^* S ∗ is a union of double cosets of H H H . Indeed, if g ∈ S ∗ g \in S^* g ∈ S ∗ , then g H ⊆ S ∗ gH \subseteq S^* g H ⊆ S ∗ . Since ( S ∗ ) − 1 = S ∗ (S^*)^{-1} = S^* ( S ∗ ) − 1 = S ∗ (because S S S is inverse closed), we also have H g ⊆ S ∗ Hg \subseteq S^* H g ⊆ S ∗ . Hence H g H ⊆ S ∗ HgH \subseteq S^* H g H ⊆ S ∗ for every g ∈ S ∗ g \in S^* g ∈ S ∗ .
We claim that the adjacency relation on the left cosets described in Lemma 7.3 is well-defined. Indeed, if g i ′ = g i h i g_i' = g_ih_i g i ′ = g i h i and g j ′ = g j h j g_j' = g_jh_j g j ′ = g j h j with h i , h j ∈ H h_i,h_j \in H h i , h j ∈ H , then ( g i ′ ) − 1 g j ′ = h i − 1 g i − 1 g j h j (g_i')^{-1}g_j' = h_i^{-1}g_i^{-1}g_jh_j ( g i ′ ) − 1 g j ′ = h i − 1 g i − 1 g j h j . Since S ∗ S^* S ∗ is a union of double cosets of H H H , we have g i − 1 g j ∈ S ∗ g_i^{-1}g_j \in S^* g i − 1 g j ∈ S ∗ if and only if ( g i ′ ) − 1 g j ′ ∈ S ∗ (g_i')^{-1}g_j' \in S^* ( g i ′ ) − 1 g j ′ ∈ S ∗ .
Remark 7.5. Further note that H H H is twin set if it is maximal, so H H H is a twin set if and only if H H H is a maximal subgroup with H ⊂ S ∗ H \subset S^* H ⊂ S ∗ so that S ∗ S^* S ∗ is a union of cosets of H H H .
Remark 7.6. If H H H is a normal subgroup of G G G , then Γ 1 \Gamma_1 Γ 1 in Lemma 7.3 is a Cayley graph Γ 1 = Γ ( G / H , S ) \Gamma_1 = \Gamma(G/H,S) Γ 1 = Γ ( G / H , S ) over the quotient group G / H G/H G / H , where S S S is the set of all cosets g i H g_iH g i H such that g i H ⊂ S ∗ g_iH \subset S^* g i H ⊂ S ∗ and g i ∉ H g_i \notin H g i ∈ / H .
If we replace “true twins” by “false twins” in Lemma 7.3 , then Γ \Gamma Γ is isomorphic to Γ 1 [ O m ] \Gamma_1[O_m] Γ 1 [ O m ] , where O m O_m O m denotes the empty graph on m = ∣ H ∣ m = |H| m = ∣ H ∣ vertices.
Lemma 7.7. With the same premise in Proposition 7.3, the following are equivalent.
(1) Pairwise, elements of H H H are false twins.
(2) H ∩ S = ∅ H \cap S = \varnothing H ∩ S = ∅ and S S S is a union of left cosets of H H H .
Moreover, if one of the above conditions holds, then Γ ≅ Γ 1 [ O m ] \Gamma\cong\Gamma_1[O_m] Γ ≅ Γ 1 [ O m ] , where m = ∣ H ∣ m = |H| m = ∣ H ∣ and the vertices of Γ 1 \Gamma_1 Γ 1 are the left cosets of H H H , and g i H g_iH g i H and g j H g_jH g j H are adjacent if and only if g i − 1 g j ∈ S g_i^{-1}g_j \in S g i − 1 g j ∈ S .
Remark 7.8. In Lemmas 7.3 and 7.7, Γ 1 \Gamma_1 Γ 1 is also vertex transitive. To see this, note that the group G G G acts on the vertices of Γ 1 \Gamma_1 Γ 1 (although this action is not faithful) and induces a transitive action on Γ 1 \Gamma_1 Γ 1 .
In general if Γ = Γ 1 [ Γ 2 ] \Gamma= \Gamma_1[\Gamma_2] Γ = Γ 1 [ Γ 2 ] where Γ 2 = K m \Gamma_2 = K_m Γ 2 = K m or O m O_m O m forms a twin set, then Γ \Gamma Γ is vertex transitive if and only if Γ 1 \Gamma_1 Γ 1 is. To see this, suppose X i X_i X i and X j X_j X j are two vertices of Γ 1 \Gamma_1 Γ 1 , and let x i ∈ X i x_i \in X_i x i ∈ X i and x j ∈ X j x_j \in X_j x j ∈ X j in Γ \Gamma Γ . Since Γ \Gamma Γ is vertex transitive, there exists f ∈ Aut ( Γ ) f \in\operatorname{Aut}(\Gamma) f ∈ Aut ( Γ ) such that f ( x i ) = x j f(x_i) = x_j f ( x i ) = x j . By Lemma 3.2 and maximality of twin sets, we have f ( X i ) = X j f(X_i) = X_j f ( X i ) = X j . Moreover, f f f permutes X 1 , … , X r X_1,\ldots,X_r X 1 , … , X r and preserves adjacency between them. Thus, f f f induces an automorphism f ˉ \bar{f} f ˉ of Γ 1 \Gamma_1 Γ 1 such that f ˉ ( X i ) = X j \bar{f}(X_i) = X_j f ˉ ( X i ) = X j . Therefore Γ 1 \Gamma_1 Γ 1 is vertex transitive. Clearly if Γ 1 \Gamma_1 Γ 1 is vertex transitive, then Γ \Gamma Γ is as well.
The proof of Lemma 7.3 can be extended to vertex-transitive graphs.
Theorem 7.9. Let Γ \Gamma Γ be a graph with a twin set X X X of size m m m . Then Γ \Gamma Γ is vertex transitive if and only if there is a vertex-transitive graph Γ 1 \Gamma_1 Γ 1 such that Γ ≅ Γ 1 [ Γ 2 ] \Gamma\cong\Gamma_1[\Gamma_2] Γ ≅ Γ 1 [ Γ 2 ] , where Γ 2 = K m \Gamma_2 = K_m Γ 2 = K m if X X X is a true twin set, and Γ 2 = O m \Gamma_2 = O_m Γ 2 = O m otherwise. In particular, V ( Γ ) V(\Gamma) V ( Γ ) can be partitioned into sets of twins of cardinality m m m .
Proof. The converse is clear, so we only prove the forward direction. We start with the case when X X X is a true twin set in Γ \Gamma Γ . By Lemmas 3.2 and 3.1, we get that for every f ∈ Aut ( Γ ) f \in\operatorname{Aut}(\Gamma) f ∈ Aut ( Γ ) , either f ( X ) = X f(X) = X f ( X ) = X or f ( X ) ∩ X = ∅ f(X) \cap X = \varnothing f ( X ) ∩ X = ∅ . Now fix x ∈ X x \in X x ∈ X . Since Γ \Gamma Γ is vertex-transitive, for every v ∈ V ( Γ ) v \in V(\Gamma) v ∈ V ( Γ ) there exists f ∈ Aut ( Γ ) f \in\operatorname{Aut}(\Gamma) f ∈ Aut ( Γ ) such that f ( x ) = v f(x) = v f ( x ) = v . Therefore
V ( Γ ) = ⋃ f ∈ Aut ( Γ ) f ( X ) . V(\Gamma) = \bigcup_{f \in\operatorname{Aut}(\Gamma)} f(X). V ( Γ ) = f ∈ Aut ( Γ ) ⋃ f ( X ) .
Let f , g ∈ Aut ( Γ ) f,g \in\operatorname{Aut}(\Gamma) f , g ∈ Aut ( Γ ) such that f ( X ) ∩ g ( X ) ≠ ∅ f(X) \cap g(X) \ne\varnothing f ( X ) ∩ g ( X ) = ∅ . Then X ∩ f − 1 g ( X ) ≠ ∅ X \cap f^{-1}g(X) \ne\varnothing X ∩ f − 1 g ( X ) = ∅ and therefore, we get f − 1 g ( X ) = X f^{-1}g(X) = X f − 1 g ( X ) = X . Thus f ( X ) = g ( X ) f(X) = g(X) f ( X ) = g ( X ) , so the distinct automorphic images of X X X form a partition
V ( Γ ) = X 1 ∪ ⋯ ∪ X r , V(\Gamma) = X_1 \cup\cdots\cup X_r, V ( Γ ) = X 1 ∪ ⋯ ∪ X r ,
where each X i X_i X i is a true twin set and ∣ X i ∣ = ∣ X ∣ = m |X_i| = |X| = m ∣ X i ∣ = ∣ X ∣ = m . Define a graph Γ 1 \Gamma_1 Γ 1 with vertex set V ( Γ 1 ) = { X 1 , … , X r } V(\Gamma_1) = \{X_1,\ldots,X_r\} V ( Γ 1 ) = { X 1 , … , X r } and two vertices X i X_i X i and X j X_j X j are adjacent in Γ 1 \Gamma_1 Γ 1 if there exists an edge in Γ \Gamma Γ between a vertex of X i X_i X i and a vertex of X j X_j X j . This is well-defined since each X i X_i X i is a twin set. Since the subgraph induced by X i X_i X i is K m K_m K m , we have Γ ≅ Γ 1 [ K m ] \Gamma\cong\Gamma_1[K_m] Γ ≅ Γ 1 [ K m ] . If X X X is instead a false twin set, the same argument gives a partition into sets X i X_i X i of false twins of cardinality m m m . In this case, the subgraph induced by each X i X_i X i is the empty graph O m O_m O m , and hence Γ ≅ Γ 1 [ O m ] \Gamma\cong\Gamma_1[O_m] Γ ≅ Γ 1 [ O m ] . In both cases, the same argument used in Remark 7.8 yields the fact that Γ 1 \Gamma_1 Γ 1 is vertex-transitive. □ \square □
Applications to sedentariness
We now characterize sedentariness in vertex-transitive graphs with twins.
Theorem 7.10. Let Γ \Gamma Γ be a vertex-transitive graph with a twin set X X X such that u , v ∈ X u,v \in X u , v ∈ X . Consider θ \theta θ in Lemma 3.3 . Then Γ \Gamma Γ is sedentary if and only if Γ ≅ Γ 1 [ Γ 2 ] \Gamma\cong\Gamma_1[\Gamma_2] Γ ≅ Γ 1 [ Γ 2 ] for some graph Γ 1 \Gamma_1 Γ 1 with n n n vertices, Γ 2 ∈ { K m , O m } \Gamma_2 \in\{K_m,O_m\} Γ 2 ∈ { K m , O m } where m = ∣ X ∣ ≥ 2 m=|X|\ge2 m = ∣ X ∣ ≥ 2 , and one of the following holds:
m ≥ 3 m \ge3 m ≥ 3 ;
m = 2 m=2 m = 2 and θ ∈ spec ( Γ 1 ) \theta\in\operatorname{spec}(\Gamma_1) θ ∈ spec ( Γ 1 ) ;
m = 2 m=2 m = 2 , θ ∉ spec ( Γ 1 ) \theta\notin\operatorname{spec}(\Gamma_1) θ ∈ / spec ( Γ 1 ) , and there are integers ℓ λ \ell_\lambda ℓ λ such that
∑ λ ∈ σ ( Γ ) ∖ { θ } ℓ λ ( λ − θ ) = 0 and ∑ λ ∈ σ ( Γ ) ∖ { θ } ℓ λ is odd; \sum_{\lambda\in\sigma(\Gamma)\setminus\{\theta\}}\ell_\lambda(\lambda-\theta)=0
\quad\text{and}\quad
\sum_{\lambda\in\sigma(\Gamma)\setminus\{\theta\}}\ell_\lambda\text{ is odd;} λ ∈ σ ( Γ ) ∖ { θ } ∑ ℓ λ ( λ − θ ) = 0 and λ ∈ σ ( Γ ) ∖ { θ } ∑ ℓ λ is odd; m = 2 m=2 m = 2 , θ ∉ spec ( Γ 1 ) \theta\notin\operatorname{spec}(\Gamma_1) θ ∈ / spec ( Γ 1 ) , Γ \Gamma Γ is integral, and the values of ν 2 ( λ − θ ) \nu_2(\lambda-\theta) ν 2 ( λ − θ ) are not constant for all λ ∈ σ ( Γ ) ∖ { θ } \lambda\in\sigma(\Gamma)\setminus\{\theta\} λ ∈ σ ( Γ ) ∖ { θ } .
Moreover, if condition (1) or (2) holds, then Γ \Gamma Γ is C C C -sedentary, where
C = 1 − 2 m + 2 ( m θ − n ( m − 1 ) ) m n C=1-\frac{2}{m}+\frac{2(m\theta-n(m-1))}{mn} C = 1 − m 2 + mn 2 ( m θ − n ( m − 1 )) and m θ m_\theta m θ is the multiplicity of θ \theta θ as an eigenvalue of Γ \Gamma Γ .
Proof. Our assumption combined with Theorem 7.9 implies that Γ ≅ Γ 1 [ Γ 2 ] \Gamma\cong\Gamma_1[\Gamma_2] Γ ≅ Γ 1 [ Γ 2 ] for some vertex-transitive graph Γ 1 \Gamma_1 Γ 1 with n n n vertices and Γ 2 ∈ { K m , O m } \Gamma_2\in\{K_m,O_m\} Γ 2 ∈ { K m , O m } , where m = ∣ X ∣ ≥ 2 m=|X|\ge2 m = ∣ X ∣ ≥ 2 . Because of vertex transitivity, Remark 4.4 implies that the support of each vertex in Γ \Gamma Γ and Γ 1 \Gamma_1 Γ 1 equals σ ( Γ ) \sigma(\Gamma) σ ( Γ ) and σ ( Γ 1 ) \sigma(\Gamma_1) σ ( Γ 1 ) , respectively. Applying Corollary 3.8 yields the result. □ \square □
A similar argument used in Theorem 7.10 combined with Theorem 3.7 yields a characterization of PST and PGST in vertex-transitive graphs with twins.
Corollary 7.11. Let Γ \Gamma Γ be a vertex-transitive graph with twins and consider θ \theta θ in Lemma 3.3 .
PGST occurs in Γ \Gamma Γ if and only if Γ ≅ Γ 1 [ Γ 2 ] \Gamma\cong\Gamma_1[\Gamma_2] Γ ≅ Γ 1 [ Γ 2 ] for some vertex-transitive graph Γ 1 \Gamma_1 Γ 1 such that θ ∉ spec ( Γ 1 ) \theta\notin\operatorname{spec}(\Gamma_1) θ ∈ / spec ( Γ 1 ) , Γ 2 ∈ { K 2 , O 2 } \Gamma_2\in\{K_2,O_2\} Γ 2 ∈ { K 2 , O 2 } , and for all integers ℓ λ \ell_\lambda ℓ λ , we have
∑ λ ∈ σ ( Γ ) ∖ { θ } ℓ λ ( λ − θ ) = 0 implies that ∑ λ ∈ σ ( Γ ) ∖ { θ } ℓ λ is even. \sum_{\lambda\in\sigma(\Gamma)\setminus\{\theta\}}\ell_\lambda(\lambda-\theta)=0
\quad\text{implies that}\quad
\sum_{\lambda\in\sigma(\Gamma)\setminus\{\theta\}}\ell_\lambda\text{ is even.} λ ∈ σ ( Γ ) ∖ { θ } ∑ ℓ λ ( λ − θ ) = 0 implies that λ ∈ σ ( Γ ) ∖ { θ } ∑ ℓ λ is even. PST occurs in Γ \Gamma Γ if and only if Γ ≅ Γ 1 [ Γ 2 ] \Gamma\cong\Gamma_1[\Gamma_2] Γ ≅ Γ 1 [ Γ 2 ] for some vertex-transitive graph Γ 1 \Gamma_1 Γ 1 such that θ ∉ σ ( Γ 1 ) \theta\notin\sigma(\Gamma_1) θ ∈ / σ ( Γ 1 ) , Γ 2 ∈ { K 2 , O 2 } \Gamma_2\in\{K_2,O_2\} Γ 2 ∈ { K 2 , O 2 } , Γ \Gamma Γ is integral, and there is an integer a a a such that ν 2 ( λ − θ ) = a \nu_2(\lambda-\theta)=a ν 2 ( λ − θ ) = a for all λ ∈ σ ( Γ ) ∖ { θ } \lambda\in\sigma(\Gamma)\setminus\{\theta\} λ ∈ σ ( Γ ) ∖ { θ } . In this case, τ = π 2 a \tau=\frac{\pi}{2^a} τ = 2 a π is a PST time.
Moreover, if PGST or PST occurs in Γ \Gamma Γ , then it occurs between every pair of twins in Γ \Gamma Γ .
We now illustrate Theorem 7.10 and Corollary 7.11 in the following examples.
Example 7.12. Let Q d Q_d Q d be the hypercube of dimension d ≥ 1 d\ge1 d ≥ 1 . It is known that
σ ( Q d ) = { d − 2 j : j = 0 , 1 , … , d } , \sigma(Q_d)=\{d-2j:j=0,1,\ldots,d\}, σ ( Q d ) = { d − 2 j : j = 0 , 1 , … , d } , and so Q d Q_d Q d is integral, and hence periodic. Moreover 0 ∉ σ ( Q d ) 0\notin\sigma(Q_d) 0 ∈ / σ ( Q d ) if and only if d d d is odd, while − 1 ∉ σ ( Q d ) -1\notin\sigma(Q_d) − 1 ∈ / σ ( Q d ) if and only if d d d is even. Making use of (4) , we get
σ ( Q d [ O 2 ] ) = { 2 ( d − 2 j ) : j = 0 , 1 , … , d } ∪ { θ = 0 } \sigma(Q_d[O_2])=\{2(d-2j):j=0,1,\ldots,d\}\cup\{\theta=0\} σ ( Q d [ O 2 ]) = { 2 ( d − 2 j ) : j = 0 , 1 , … , d } ∪ { θ = 0 } and
σ ( Q d [ K 2 ] ) = { 2 ( d − 2 j ) + 1 : j = 0 , 1 , … , d } ∪ { θ = − 1 } . \sigma(Q_d[K_2])=\{2(d-2j)+1:j=0,1,\ldots,d\}\cup\{\theta=-1\}. σ ( Q d [ K 2 ]) = { 2 ( d − 2 j ) + 1 : j = 0 , 1 , … , d } ∪ { θ = − 1 } . For Q d [ O 2 ] Q_d[O_2] Q d [ O 2 ] , we have ν 2 ( λ − θ ) = ν 2 ( 2 ( d − 2 j ) − 0 ) \nu_2(\lambda-\theta)=\nu_2(2(d-2j)-0) ν 2 ( λ − θ ) = ν 2 ( 2 ( d − 2 j ) − 0 ) is a constant a a a for all j ∈ { 0 , 1 , … , d } j\in\{0,1,\ldots,d\} j ∈ { 0 , 1 , … , d } if and only if d d d is odd, in which case a = 1 a=1 a = 1 . For Q d [ K 2 ] Q_d[K_2] Q d [ K 2 ] , we have ν 2 ( λ − θ ) = ν 2 ( 2 ( d − 2 j + 1 ) \nu_2(\lambda-\theta)=\nu_2(2(d-2j+1) ν 2 ( λ − θ ) = ν 2 ( 2 ( d − 2 j + 1 ) is a constant a a a for all j ∈ { 0 , 1 , … , d } j\in\{0,1,\ldots,d\} j ∈ { 0 , 1 , … , d } if and only if d d d is even, in which case a = 1 a=1 a = 1 . Applying
Corollary 7.11(2). PST occurs in Q d [ O 2 ] Q_d[O_2] Q d [ O 2 ] (resp., Q d [ K 2 ] Q_d[K_2] Q d [ K 2 ] ) if and only if d d d is odd (resp., even), in which case, it occurs between every pair of twins at time π 2 \frac{\pi}{2} 2 π . Moreover, by Theorem 7.10 , Q d [ O m ] Q_d[O_m] Q d [ O m ] (resp., Q d [ K m ] Q_d[K_m] Q d [ K m ] ) is sedentary if and only if m ≥ 3 m \ge3 m ≥ 3 or d d d is even (resp., odd).
Example 7.13. As σ ( K n [ O 2 ] ) = { 2 ( n − 1 ) , − 2 } ∪ { θ = 0 } \sigma(K_n[O_2]) = \{2(n-1),-2\} \cup\{\theta=0\} σ ( K n [ O 2 ]) = { 2 ( n − 1 ) , − 2 } ∪ { θ = 0 } , the same argument used in Example 7.12 yields PST in K n [ O 2 ] K_n[O_2] K n [ O 2 ] if and only if n n n is even, in which case, it occurs between every pair of twins at π 2 \frac{\pi}{2} 2 π . Also, K n [ O m ] K_n[O_m] K n [ O m ] is sedentary if and only if m ≥ 3 m \ge3 m ≥ 3 or n n n is odd.
Example 7.14. Let C n C_n C n be the cycle on n n n vertices. It is known that C n [ O 2 ] C_n[O_2] C n [ O 2 ] does not admit PGST [5 Theorem 7] . Thus each vertex in C n [ O m ] C_n[O_m] C n [ O m ] is sedentary for all m ≥ 2 m \ge2 m ≥ 2 by Theorem 3.4 .
We now complement Theorem 6.3 by showing that if ∣ G ∣ |G| ∣ G ∣ is even, then there exists a subset S ⊂ G S \subset G S ⊂ G such that Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is connected and not sedentary.
Corollary 7.15. If ∣ G ∣ |G| ∣ G ∣ is even, then there exists a subset S S S such that Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is connected and not sedentary.
Proof. First, suppose ∣ G ∣ = 4 k |G|=4k ∣ G ∣ = 4 k for some integer k k k . Let z ∈ G z \in G z ∈ G such that z 2 = 1 z^2=1 z 2 = 1 , H = { 1 , z } H=\{1,z\} H = { 1 , z } and consider Γ = Γ ( G , S ) \Gamma=\Gamma(G,S) Γ = Γ ( G , S ) where S = G ∖ H S=G \setminus H S = G ∖ H . By Lemma 7.7, Γ ≅ K 2 k [ O 2 ] \Gamma\cong K_{2k}[O_2] Γ ≅ K 2 k [ O 2 ] . Since Γ \Gamma Γ is a cocktail party graph, it is not sedentary by [26 Corollary 4] . Next, let ∣ G ∣ = 2 k |G|=2k ∣ G ∣ = 2 k where k k k is odd. Let z ∈ G z \in G z ∈ G such that z 2 = 1 z^2=1 z 2 = 1 . We first show that G G G has a normal subgroup of index 2. The action on G G G by itself via left multiplication induces a group homomorphism ℓ : G → S 2 k \ell:G \to S_{2k} ℓ : G → S 2 k . For each pair ( g , z g ) (g,zg) ( g , z g ) , z z z acts as a transposition. The sign of ℓ ( z ) \ell(z) ℓ ( z ) is therefore equal to ( − 1 ) k = − 1 (-1)^k=-1 ( − 1 ) k = − 1 . This shows that the composition map ℓ : G → S 2 k → { ± 1 } \ell:G \to S_{2k} \to\{\pm1\} ℓ : G → S 2 k → { ± 1 } is surjective. Let K K K be the kernel of this map. Then, K K K is a normal subgroup of index 2 in G G G . Let S = ( K ∖ { 1 } ) ∪ { z } S=(K \setminus\{1\}) \cup\{z\} S = ( K ∖ { 1 }) ∪ { z } . Then, S S S is inverse closed and any two elements in K K K are adjacent. Similarly, any two elements in z K zK z K are adjacent. Furthermore, each element in K K K is adjacent to exactly one element in z K zK z K . Thus, Γ ( G , S ) ≅ K 2 □ K k \Gamma(G,S) \cong K_2 \square K_k Γ ( G , S ) ≅ K 2 □ K k , which is not sedentary. In both cases, Γ \Gamma Γ is connected. □ \square □
Remark 7.16. Without the connectedness requirement, we may simply take S = { z } S=\{z\} S = { z } where z 2 = 1 z^2=1 z 2 = 1 . In this case, Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is a disjoint union of copies of K 2 K_2 K 2 , and hence not sedentary.
Modular properties of eigenvalues
In Theorem 3.6 , we showed that for PST to occur between twins u u u and v v v in a graph Γ \Gamma Γ , it must be that ν 2 ( λ − θ ) \nu_2(\lambda-\theta) ν 2 ( λ − θ ) is equal for all λ ∈ Φ u ∖ { θ } \lambda\in\Phi_u \setminus\{\theta\} λ ∈ Φ u ∖ { θ } . In this penultimate section, we investigate whether this modular property holds in general for integral graphs and Cayley graphs.
Integral graphs
We now examine whether the above-mentioned modular property holds for integral graphs.
Lemma 8.1. Let Γ \Gamma Γ be an integral graph with eigenvalues λ 1 , … , λ n \lambda_1,\ldots,\lambda_n λ 1 , … , λ n . If n = ∣ V ( Γ ) ∣ n=|V(\Gamma)| n = ∣ V ( Γ ) ∣ is odd, then the following statements hold.
(1) There is no a ∈ Z a \in\mathbb{Z} a ∈ Z such that ν 2 ( λ j ) = a \nu_2(\lambda_j)=a ν 2 ( λ j ) = a for all $1 \le j \le n.
(2) If some λ i \lambda_i λ i is odd and λ j ≠ − 1 \lambda_j \ne-1 λ j = − 1 for all 1 ≤ j ≤ n 1 \le j \le n 1 ≤ j ≤ n , then there is no a ∈ Z a \in\mathbb{Z} a ∈ Z such that ν 2 ( λ j + 1 ) = a \nu_2(\lambda_j+1)=a ν 2 ( λ j + 1 ) = a for all $1 \le j \le n.
(3) If λ i = 0 \lambda_i = 0 λ i = 0 has even multiplicity, then there is no a ∈ Z a \in\mathbb{Z} a ∈ Z such that ν 2 ( λ j ) = a \nu_2(\lambda_j) = a ν 2 ( λ j ) = a for all λ j ≠ 0 \lambda_j \ne0 λ j = 0 .
(4) If λ i = − 1 \lambda_i = -1 λ i = − 1 has even multiplicity and for some ℓ ≠ i \ell\ne i ℓ = i , we have λ ℓ \lambda_\ell λ ℓ is odd and λ ℓ ≠ − 1 \lambda_\ell\ne-1 λ ℓ = − 1 , then there is no a ∈ Z a \in\mathbb{Z} a ∈ Z such that ν 2 ( λ j + 1 ) = a \nu_2(\lambda_j + 1) = a ν 2 ( λ j + 1 ) = a for all λ j ≠ − 1 \lambda_j \ne-1 λ j = − 1 .
Proof. We prove (1) by way of contradiction. Suppose there is an integer a a a such that ν 2 ( λ j ) = a \nu_2(\lambda_j) = a ν 2 ( λ j ) = a for all 1 ≤ j ≤ n 1 \le j \le n 1 ≤ j ≤ n . Let λ j ′ = λ j / 2 a \lambda'_j = \lambda_j/2^a λ j ′ = λ j / 2 a . Then each λ j ′ \lambda'_j λ j ′ is an odd integer. Since n n n is odd, we get
∑ j = 1 n λ j ′ ≡ ∑ j = 1 n 1 = n ≡ 1 ( m o d 2 ) . \sum_{j=1}^{n} \lambda'_j \equiv\sum_{j=1}^{n} 1 = n \equiv1 \pmod{2}. j = 1 ∑ n λ j ′ ≡ j = 1 ∑ n 1 = n ≡ 1 ( mod 2 ) .
But since the trace of A ( Γ ) A(\Gamma) A ( Γ ) is zero, we get
∑ j = 1 n λ j ′ = 1 2 a ∑ j = 1 n λ j = 0 , \sum_{j=1}^{n} \lambda'_j = \frac{1}{2^a}\sum_{j=1}^{n}\lambda_j = 0, j = 1 ∑ n λ j ′ = 2 a 1 j = 1 ∑ n λ j = 0 ,
a contradiction. To prove (2), suppose that λ i \lambda_i λ i is odd and there exists an integer a a a such that ν 2 ( λ j + 1 ) = a \nu_2(\lambda_j + 1) = a ν 2 ( λ j + 1 ) = a for all 1 ≤ j ≤ n 1 \le j \le n 1 ≤ j ≤ n . Since λ i \lambda_i λ i is odd, we know that a ≥ 1 a \ge1 a ≥ 1 . Consequently λ j \lambda_j λ j is odd for all 1 ≤ j ≤ n 1 \le j \le n 1 ≤ j ≤ n . Since n n n is odd, we get that ∑ j = 1 n λ j \sum_{j=1}^{n}\lambda_j ∑ j = 1 n λ j is odd, which is impossible because the trace of A ( Γ ) A(\Gamma) A ( Γ ) is zero. Lastly, suppose 0 0 0 is an eigenvalue with even multiplicity. If there is an a ∈ Z a \in\mathbb{Z} a ∈ Z such that ν 2 ( λ i ) = a \nu_2(\lambda_i) = a ν 2 ( λ i ) = a for all λ i ≠ 0 \lambda_i \ne0 λ i = 0 , then a similar argument used in the proof of (1) yields the desired conclusion. Meanwhile, if − 1 -1 − 1 is an eigenvalue of Γ \Gamma Γ and λ j ≠ − 1 \lambda_j \ne-1 λ j = − 1 is odd for some j j j , then the same argument used in the proof of (2) yields the desired conclusion. □
Remark 8.2. Lemma 8.1(2) is false if the condition that at least one eigenvalue is odd is not met. For example, the star graphs K 1 , 4 k 2 K_{1,4k^2} K 1 , 4 k 2 have an odd number of vertices and σ ( K 1 , 4 k 2 ) = { 2 k , − 2 k , 0 } \sigma(K_{1,4k^2}) = \{2k, -2k, 0\} σ ( K 1 , 4 k 2 ) = { 2 k , − 2 k , 0 } . So no eigenvalue of K 1 , 4 k 2 K_{1,4k^2} K 1 , 4 k 2 is odd and ν 2 ( μ i + 1 ) = 0 \nu_2(\mu_i + 1) = 0 ν 2 ( μ i + 1 ) = 0 for all i i i .
Corollary 8.3. Let Γ \Gamma Γ be an integral graph where ∣ V ( Γ ) ∣ |V(\Gamma)| ∣ V ( Γ ) ∣ is odd. If vertex u u u has a false twin in Γ \Gamma Γ such that Φ u = σ ( Γ ) \Phi_u = \sigma(\Gamma) Φ u = σ ( Γ ) and 0 ∈ σ ( Γ ) 0 \in\sigma(\Gamma) 0 ∈ σ ( Γ ) has even multiplicity, then u u u is sedentary in Γ \Gamma Γ . If vertex u u u has a true twin in Γ \Gamma Γ such that Φ u = σ ( Γ ) \Phi_u = \sigma(\Gamma) Φ u = σ ( Γ ) and some λ ∈ σ ( Γ ) ∖ { − 1 } \lambda\in\sigma(\Gamma)\setminus\{-1\} λ ∈ σ ( Γ ) ∖ { − 1 } is odd, then u u u is sedentary in Γ \Gamma Γ .
Proof. If u u u belongs to a false twin set of size at least three, then u u u is sedentary by Theorem 3.5 . Thus, we may assume that the twin set containing u u u has size two. By assumption, Φ u = σ ( Γ ) \Phi_u = \sigma(\Gamma) Φ u = σ ( Γ ) and θ = 0 \theta= 0 θ = 0 has even multiplicity. If u u u admits PST in Γ \Gamma Γ , then Theorem 3.6 yields ν 2 ( λ − θ ) = a \nu_2(\lambda- \theta) = a ν 2 ( λ − θ ) = a for all λ ∈ σ ( Γ ) ∖ { θ } \lambda\in\sigma(\Gamma)\setminus\{\theta\} λ ∈ σ ( Γ ) ∖ { θ } , a contradiction to Lemma 8.1(3). The same argument applies if u u u has a true twin in Γ \Gamma Γ with Φ u = σ ( Γ ) \Phi_u = \sigma(\Gamma) Φ u = σ ( Γ ) , θ = − 1 \theta= -1 θ = − 1 , and some λ ∈ σ ( Γ ) ∖ { θ } \lambda\in\sigma(\Gamma)\setminus\{\theta\} λ ∈ σ ( Γ ) ∖ { θ } is odd. In both cases, u u u is not involved in PST, and so it is sedentary in Γ \Gamma Γ by Theorem 3.4 . □
We are now ready to prove the following result.
Theorem 8.4. Suppose Γ = Γ 1 [ Γ 2 ] \Gamma= \Gamma_1[\Gamma_2] Γ = Γ 1 [ Γ 2 ] is an integral graph where Γ 2 ∈ { O 2 , K 2 } \Gamma_2 \in\{O_2, K_2\} Γ 2 ∈ { O 2 , K 2 } . If ∣ V ( Γ ) ∣ ≡ 2 ( m o d 4 ) |V(\Gamma)| \equiv2 \pmod{4} ∣ V ( Γ ) ∣ ≡ 2 ( mod 4 ) and ( u , j ) ∈ V ( Γ ) (u,j) \in V(\Gamma) ( u , j ) ∈ V ( Γ ) such that Φ e u ( Γ 1 ) = spec ( Γ 1 ) \Phi_{e_u}(\Gamma_1) = \operatorname{spec}(\Gamma_1) Φ e u ( Γ 1 ) = spec ( Γ 1 ) , then the following hold.
(1) If Γ = Γ 1 [ O 2 ] \Gamma= \Gamma_1[O_2] Γ = Γ 1 [ O 2 ] , then vertex ( u , j ) (u,j) ( u , j ) is sedentary in Γ \Gamma Γ .
(2) If Γ = Γ 1 [ K 2 ] \Gamma= \Gamma_1[K_2] Γ = Γ 1 [ K 2 ] , then vertex u u u is sedentary in Γ \Gamma Γ if and only if either (i) − 1 ∈ spec ( Γ 1 ) -1 \in\operatorname{spec}(\Gamma_1) − 1 ∈ spec ( Γ 1 ) or (ii) − 1 ∉ spec ( Γ 1 ) -1 \notin\operatorname{spec}(\Gamma_1) − 1 ∈ / spec ( Γ 1 ) and some eigenvalue in spec ( Γ 1 ) \operatorname{spec}(\Gamma_1) spec ( Γ 1 ) is odd.
Proof. Let Γ = Γ 1 [ Γ 2 ] \Gamma= \Gamma_1[\Gamma_2] Γ = Γ 1 [ Γ 2 ] , where Γ 2 ∈ { O 2 , K 2 } \Gamma_2 \in\{O_2,K_2\} Γ 2 ∈ { O 2 , K 2 } . Since ∣ V ( Γ ) ∣ ≡ 2 ( m o d 4 ) |V(\Gamma)| \equiv2 \pmod{4} ∣ V ( Γ ) ∣ ≡ 2 ( mod 4 ) , it follows that ∣ V ( Γ 1 ) ∣ |V(\Gamma_1)| ∣ V ( Γ 1 ) ∣ is odd. From (2.2), spec ( Γ 1 [ O 2 ] ) = { 2 μ : μ ∈ spec ( Γ 1 ) } ∪ { θ = 0 } \operatorname{spec}(\Gamma_1[O_2]) = \{2\mu: \mu\in\operatorname{spec}(\Gamma_1)\} \cup\{\theta= 0\} spec ( Γ 1 [ O 2 ]) = { 2 μ : μ ∈ spec ( Γ 1 )} ∪ { θ = 0 } and spec ( Γ 1 [ K 2 ] ) = { 2 μ + 1 : μ ∈ spec ( Γ 1 ) } ∪ { θ = − 1 } \operatorname{spec}(\Gamma_1[K_2]) = \{2\mu+ 1 : \mu\in\operatorname{spec}(\Gamma_1)\} \cup\{\theta= -1\} spec ( Γ 1 [ K 2 ]) = { 2 μ + 1 : μ ∈ spec ( Γ 1 )} ∪ { θ = − 1 } . Since σ ( Γ ) ⊆ Z \sigma(\Gamma) \subseteq\mathbb{Z} σ ( Γ ) ⊆ Z , it follows from the spectra of Γ 1 [ O 2 ] \Gamma_1[O_2] Γ 1 [ O 2 ] and Γ 1 [ K 2 ] \Gamma_1[K_2] Γ 1 [ K 2 ] that spec ( Γ 1 ) ⊆ Z \operatorname{spec}(\Gamma_1) \subseteq\mathbb{Z} spec ( Γ 1 ) ⊆ Z . Now, if (a) Γ = Γ 1 [ O 2 ] \Gamma= \Gamma_1[O_2] Γ = Γ 1 [ O 2 ] and 0 ∈ spec ( Γ 1 ) 0 \in\operatorname{spec}(\Gamma_1) 0 ∈ spec ( Γ 1 ) or (b) Γ = Γ 1 [ K 2 ] \Gamma= \Gamma_1[K_2] Γ = Γ 1 [ K 2 ] and − 1 ∈ spec ( Γ 1 ) -1 \in\operatorname{spec}(\Gamma_1) − 1 ∈ spec ( Γ 1 ) , then vertex ( u , j ) (u,j) ( u , j ) is sedentary in Γ \Gamma Γ by Corollary 3.8. So to prove (1), it suffices to consider the case when 0 ∉ spec ( Γ 1 ) 0 \notin\operatorname{spec}(\Gamma_1) 0 ∈ / spec ( Γ 1 ) , and to prove (2), it suffices to consider the case when − 1 ∉ spec ( Γ 1 ) -1 \notin\operatorname{spec}(\Gamma_1) − 1 ∈ / spec ( Γ 1 ) and some eigenvalue of spec ( Γ 1 ) \operatorname{spec}(\Gamma_1) spec ( Γ 1 ) is odd.
Assume that condition (2i) or (2ii) above holds. By way of contradiction, suppose u u u is not sedentary in Γ \Gamma Γ . Since Φ e ( u , j ) ( Γ ) ⊆ Z \Phi_{e_{(u,j)}}(\Gamma) \subseteq\mathbb{Z} Φ e ( u , j ) ( Γ ) ⊆ Z , this assumption is equivalent to vertex u u u being involved in PST in Γ \Gamma Γ by Theorem 3.4. By Theorem 3.6, ν 2 ( λ − θ ) \nu_2(\lambda-\theta) ν 2 ( λ − θ ) is a constant for all λ ∈ σ ( Γ ) ∖ { θ } \lambda\in\sigma(\Gamma)\setminus\{\theta\} λ ∈ σ ( Γ ) ∖ { θ } . Let us first deal with the case when Γ = Γ 1 [ O 2 ] \Gamma= \Gamma_1[O_2] Γ = Γ 1 [ O 2 ] , and let us assume 0 ∉ σ ( Γ 1 ) 0 \notin\sigma(\Gamma_1) 0 ∈ / σ ( Γ 1 ) . The condition that ν 2 ( λ ) \nu_2(\lambda) ν 2 ( λ ) is a constant for all λ ∈ σ ( Γ ) ∖ { 0 } \lambda\in\sigma(\Gamma)\setminus\{0\} λ ∈ σ ( Γ ) ∖ { 0 } is equivalent to ν 2 ( μ ) \nu_2(\mu) ν 2 ( μ ) is a constant for all μ ∈ spec ( Γ 1 ) \mu\in\operatorname{spec}(\Gamma_1) μ ∈ spec ( Γ 1 ) . Since ∣ V ( Γ 1 ) ∣ |V(\Gamma_1)| ∣ V ( Γ 1 ) ∣ is odd, Lemma 8.1(1) yields a contradiction. Next, suppose Γ = Γ 1 [ K 2 ] \Gamma= \Gamma_1[K_2] Γ = Γ 1 [ K 2 ] and assume − 1 ∉ spec ( Γ 1 ) -1 \notin\operatorname{spec}(\Gamma_1) − 1 ∈ / spec ( Γ 1 ) . The condition that ν 2 ( λ + 1 ) \nu_2(\lambda+1) ν 2 ( λ + 1 ) is a constant for all λ ∈ σ ( Γ ) ∖ { − 1 } \lambda\in\sigma(\Gamma)\setminus\{-1\} λ ∈ σ ( Γ ) ∖ { − 1 } is equivalent to ν 2 ( μ + 1 ) \nu_2(\mu+1) ν 2 ( μ + 1 ) is a constant for all μ ∈ σ ( Γ 1 ) \mu\in\sigma(\Gamma_1) μ ∈ σ ( Γ 1 ) . If some eigenvalue in σ ( Γ 1 ) \sigma(\Gamma_1) σ ( Γ 1 ) is odd, then because ∣ V ( Γ 1 ) ∣ |V(\Gamma_1)| ∣ V ( Γ 1 ) ∣ is odd and − 1 ∉ σ ( Γ 1 ) -1 \notin\sigma(\Gamma_1) − 1 ∈ / σ ( Γ 1 ) , applying Lemma 8.1(2) again yields a contradiction. In both cases, vertex u u u is not involved in PST, and hence it is sedentary by Theorem 3.4. To complete the proof of (2), we now show that Γ 1 [ K 2 ] \Gamma_1[K_2] Γ 1 [ K 2 ] is not sedentary whenever − 1 ∉ spec ( Γ 1 ) -1 \notin\operatorname{spec}(\Gamma_1) − 1 ∈ / spec ( Γ 1 ) and spec ( Γ 1 ) \operatorname{spec}(\Gamma_1) spec ( Γ 1 ) consists of all even integers. Indeed, if Γ = Γ 1 [ K 2 ] \Gamma= \Gamma_1[K_2] Γ = Γ 1 [ K 2 ] , then σ ( Γ ) = { 2 μ + 1 : μ ∈ spec ( Γ 1 ) } ∪ { θ = − 1 } \sigma(\Gamma) = \{2\mu+ 1 : \mu\in\operatorname{spec}(\Gamma_1)\} \cup\{\theta= -1\} σ ( Γ ) = { 2 μ + 1 : μ ∈ spec ( Γ 1 )} ∪ { θ = − 1 } , and as each μ ∈ spec ( Γ 1 ) \mu\in\operatorname{spec}(\Gamma_1) μ ∈ spec ( Γ 1 ) is even, we get ν 2 ( 2 μ + 1 − ( − 1 ) ) = 1 + ν 2 ( μ + 1 ) = 1 \nu_2(2\mu+ 1 - (-1)) = 1 + \nu_2(\mu+ 1) = 1 ν 2 ( 2 μ + 1 − ( − 1 )) = 1 + ν 2 ( μ + 1 ) = 1 . Invoking Theorem 3.7 completes the proof. □
Recall that a subset S S S of G G G is called normal if S S S is stable under conjugation. In other words, S S S is a union of some conjugacy classes in G G G . We say that Γ = Γ ( G , S ) \Gamma= \Gamma(G,S) Γ = Γ ( G , S ) is a normal Cayley graph if S S S is a normal subset of G G G .
Example 8.5. Let Γ = Γ ( G , S ) \Gamma= \Gamma(G,S) Γ = Γ ( G , S ) be an integral normal Cayley graph of odd order. Then Γ \Gamma Γ has an odd eigenvalue [3 ] . Combining this with Theorems 8.4 and 3.5(1), we get that Γ [ O m ] \Gamma[O_m] Γ [ O m ] and Γ [ K m ] \Gamma[K_m] Γ [ K m ] are sedentary for all m ≥ 2 m \ge2 m ≥ 2 .
Cayley graphs
Here, we investigate whether the condition that all eigenvalues of a Cayley graph Γ \Gamma Γ are divisible by some prime p p p has structural implications on Γ \Gamma Γ .
Corollary 8.6. Let G G G be a group such that ∣ G ∣ ≡ 2 ( m o d 4 ) |G| \equiv2 \pmod{4} ∣ G ∣ ≡ 2 ( mod 4 ) , ∣ G ∣ > 2 |G| > 2 ∣ G ∣ > 2 , and G G G has a normal 2-Sylow subgroup; say P P P . If Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is an integral normal Cayley graph with twins such that S ⊈ P S \not\subseteq P S ⊆ P , then Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is sedentary.
Proof. Let ∣ G ∣ ≡ 2 ( m o d 4 ) |G| \equiv2 \pmod{4} ∣ G ∣ ≡ 2 ( mod 4 ) and Γ = Γ ( G , S ) \Gamma= \Gamma(G,S) Γ = Γ ( G , S ) be an integral normal Cayley graph with twins. Suppose to the contrary that Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is not sedentary. By Proposition 7.2, we know that there exists a non-trivial subgroup H H H of G G G such that H H H is a set of twins. Since Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is not sedentary, we have ∣ H ∣ = 2 |H| = 2 ∣ H ∣ = 2 by Theorem 7.10. By assumption, ∣ G ∣ ≡ 2 ( m o d 4 ) |G| \equiv2 \pmod{4} ∣ G ∣ ≡ 2 ( mod 4 ) and ∣ H ∣ = 2 |H| = 2 ∣ H ∣ = 2 , we know that H H H is a 2-Sylow subgroup of G G G . Since all 2-Sylow subgroups are conjugate and P P P is normal, we must have P = H P = H P = H . By Lemma 7.3 and Lemma 7.7, Remark 7.6 and (2.2), we have that Γ = Γ 1 [ Γ 2 ] \Gamma= \Gamma_1[\Gamma_2] Γ = Γ 1 [ Γ 2 ] where Γ 2 ∈ { O 2 , K 2 } \Gamma_2 \in\{O_2,K_2\} Γ 2 ∈ { O 2 , K 2 } , ∣ Γ 1 ∣ |\Gamma_1| ∣ Γ 1 ∣ is odd, and Γ 1 \Gamma_1 Γ 1 is a Cayley graph over G / H G/H G / H . More specifically, we have Γ 1 ≅ Γ ( G / H , S ′ ) \Gamma_1 \cong\Gamma(G/H,S') Γ 1 ≅ Γ ( G / H , S ′ ) where S ′ S' S ′ is the image of S S S under the projection map G → G / H G \to G/H G → G / H (excluding the coset e H eH eH ). Moreover, since S S S is a union of conjugacy classes, so is S ′ S' S ′ . Additionally, since S ⊄ P S \not\subset P S ⊂ P , S ′ S' S ′ is not empty. This shows that Γ 1 \Gamma_1 Γ 1 is an integral normal Cayley graph over G / H G/H G / H . Since ∣ G / H ∣ |G/H| ∣ G / H ∣ is odd and S ′ S' S ′ is not empty, Γ 1 \Gamma_1 Γ 1 has an odd eigenvalue by [3 ] . By Theorem 8.4 , we conclude that Γ \Gamma Γ must be sedentary. □
Let Γ = Γ ( G , S ) \Gamma= \Gamma(G,S) Γ = Γ ( G , S ) be a integral Cayley graph and H H H be a subgroup of G G G that is a twin set in Γ \Gamma Γ with m = ∣ H ∣ m = |H| m = ∣ H ∣ . By (4) , the eigenvalues of Γ \Gamma Γ are multiples of m m m if Γ ≅ Γ 1 [ O m ] \Gamma\cong\Gamma_1[O_m] Γ ≅ Γ 1 [ O m ] , and congruent to − 1 -1 − 1 modulo m m m otherwise. This prompts us to ask: to what extent does the converse of this fact hold? That is, if all eigenvalues of Γ \Gamma Γ are multiples of m m m , then does Γ \Gamma Γ contain a false twin set of size m m m ? Similarly, if all eigenvalues of Γ \Gamma Γ are congruent to − 1 -1 − 1 modulo m m m , does Γ \Gamma Γ contain a true twin set of size m m m ? We answer these questions to the negative by characterizing the occurrence of this modular property on σ ( Γ ) \sigma(\Gamma) σ ( Γ ) under mild assumptions on S S S .
Theorem 8.7. Let G G G be a finite group, p p p be a prime that divides ∣ G ∣ |G| ∣ G ∣ , and P P P be a normal p p p -Sylow subgroup of G G G . Let S ⊂ G S \subset G S ⊂ G be such that Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is integral. Let A S = ∑ s ∈ S s ∈ Z [ G ] A_S = \sum_{s \in S} s \in\mathbb{Z}[G] A S = ∑ s ∈ S s ∈ Z [ G ] and let A ‾ S \overline{A}_S A S be its image in F p [ G ] \mathbb{F}_p[G] F p [ G ] . The following statements hold.
If A ‾ S \overline{A}_S A S belongs to the kernel of the natural map Φ : F p [ G ] → F p [ G / P ] \Phi: \mathbb{F}_p[G] \to\mathbb{F}_p[G/P] Φ : F p [ G ] → F p [ G / P ] , then all eigenvalues of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) are divisible by p p p .
If, in addition, Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is normal, then the converse also holds. Equivalently, all eigenvalues of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) are divisible by p p p if and only if A ‾ S ∈ ker ( Φ ) \overline{A}_S \in\ker(\Phi) A S ∈ ker ( Φ ) .
Moreover, the condition A ‾ S ∈ ker ( Φ ) \overline{A}_S \in\ker(\Phi) A S ∈ ker ( Φ ) is equivalent to the condition that for every coset g P gP g P ,
∣ S ∩ g P ∣ ≡ 0 ( m o d p ) . |S \cap gP| \equiv0 \pmod p. ∣ S ∩ g P ∣ ≡ 0 ( mod p ) .
Proof. Let A A A be the adjacency matrix of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) . This is the matrix of the linear map
Q [ G ] → Q [ G ] , g ↦ g A S . \mathbb{Q}[G] \to\mathbb{Q}[G], \qquad g \mapsto gA_S. Q [ G ] → Q [ G ] , g ↦ g A S .
Let f ( x ) = ∏ i = 1 ∣ G ∣ ( x − λ i ) f(x) = \prod_{i=1}^{|G|}(x-\lambda_i) f ( x ) = ∏ i = 1 ∣ G ∣ ( x − λ i ) be the characteristic polynomial of Γ \Gamma Γ . Since P P P is a normal p p p -Sylow subgroup, the Jacobson radical of F p [ G ] \mathbb{F}_p[G] F p [ G ] is the kernel of the following map
J ( F p [ G ] ) = ker ( Φ : F p [ G ] → F p [ G / P ] ) . J(\mathbb{F}_p[G]) = \ker\left(\Phi: \mathbb{F}_p[G] \to\mathbb{F}_p[G/P]\right). J ( F p [ G ]) = ker ( Φ : F p [ G ] → F p [ G / P ] ) .
(see [33 Theorem 16.6] ). If A ‾ S ∈ ker ( Φ ) \overline{A}_S \in\ker(\Phi) A S ∈ ker ( Φ ) , then A ‾ S ∈ J ( F p [ G ] ) \overline{A}_S \in J(\mathbb{F}_p[G]) A S ∈ J ( F p [ G ]) , and so A ‾ S \overline{A}_S A S is nilpotent. Thus
f ( x ) ≡ x ∣ G ∣ ( m o d p ) , f(x) \equiv x^{|G|} \pmod p, f ( x ) ≡ x ∣ G ∣ ( mod p ) ,
which implies that all the integer eigenvalues λ j \lambda_j λ j are divisible by p p p .
Conversely, suppose that Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is normal and all λ j \lambda_j λ j are divisible by p p p . Then
f ( x ) ≡ x ∣ G ∣ ( m o d p ) . f(x) \equiv x^{|G|} \pmod p. f ( x ) ≡ x ∣ G ∣ ( mod p ) .
By the Cayley–Hamilton theorem, A ‾ S \overline{A}_S A S is nilpotent in F p [ G ] \mathbb{F}_p[G] F p [ G ] . Since Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is normal, S S S is a union of conjugacy classes. Thus, S S S is stable under conjugation, and so A ‾ S \overline{A}_S A S is central, implying that A ‾ S ∈ J ( F p [ G ] ) \overline{A}_S \in J(\mathbb{F}_p[G]) A S ∈ J ( F p [ G ]) . Thus A ‾ S ∈ ker ( Φ ) \overline{A}_S \in\ker(\Phi) A S ∈ ker ( Φ ) . Finally,
Φ ( A ‾ S ) = ∑ g P ∈ G / P ∣ S ∩ g P ∣ g P , \Phi(\overline{A}_S) = \sum_{gP \in G/P} |S \cap gP|\,gP, Φ ( A S ) = g P ∈ G / P ∑ ∣ S ∩ g P ∣ g P ,
where the coefficients are taken modulo p p p . Hence Φ ( A ‾ S ) = 0 \Phi(\overline{A}_S) = 0 Φ ( A S ) = 0 if and only if for every coset g P gP g P ,
∣ S ∩ g P ∣ ≡ 0 ( m o d p ) . |S \cap gP| \equiv0 \pmod p. ∣ S ∩ g P ∣ ≡ 0 ( mod p ) .
We now derive corollaries of Theorem 8.7.
Corollary 8.8. Let p p p be a prime and G G G be a finite group such that gcd ( p , ∣ G ∣ ) = 1 \operatorname{gcd}(p,|G|)=1 gcd ( p , ∣ G ∣ ) = 1 . If Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is an integral normal Cayley graph such that S ≠ ∅ S \ne\varnothing S = ∅ , then Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) has at least one eigenvalue which is not a multiple of p p p .
Proof. In this case, P = { 1 } P=\{1\} P = { 1 } is the only p p p -Sylow subgroup of G G G . Since S S S is nonempty, we can choose s ∈ S s \in S s ∈ S . Then ∣ S ∩ s P ∣ = 1 |S \cap sP|=1 ∣ S ∩ s P ∣ = 1 which is not a multiple of p p p . Therefore, by Theorem 8.7 , we know that Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) has an eigenvalue which is not a multiple of p p p . □
Taking p = 2 p=2 p = 2 in Corollary 8.8 recovers a result in [3 ] , which states that an integral normal Cayley graph on an odd number of vertices has an odd eigenvalue.
Next, we deal with the case where p ∣ ∣ G ∣ p \mid|G| p ∣ ∣ G ∣ but p 2 ∤ ∣ G ∣ p^2 \nmid|G| p 2 ∤ ∣ G ∣ . In this case, we give a partial answer to the question raised immediately after Corollary 8.6. Namely, if all eigenvalues of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) are multiples of p p p , does it imply that Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) has a set of twins of size p p p ?
Corollary 8.9. Let G G G be a finite group and p p p a prime number with p ∣ ∣ G ∣ p \mid|G| p ∣ ∣ G ∣ and p 2 ∤ ∣ G ∣ p^2 \nmid|G| p 2 ∤ ∣ G ∣ . Suppose that G G G has a normal p p p -Sylow subgroup P P P such that ∣ P ∣ = p |P|=p ∣ P ∣ = p . If Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is an integral normal Cayley graph, then the following hold.
All eigenvalues of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) are multiples of p p p if and only if Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is isomorphic to Γ 1 [ O p ] \Gamma_1[O_p] Γ 1 [ O p ] where Γ 1 \Gamma_1 Γ 1 is a Cayley graph on G / P G/P G / P .
All eigenvalues of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) are congruent to − 1 -1 − 1 modulo p p p if and only if Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is isomorphic to Γ 1 [ K p ] \Gamma_1[K_p] Γ 1 [ K p ] where Γ 1 \Gamma_1 Γ 1 is a Cayley graph on G / P G/P G / P .
Proof. We first prove (1). First, if Γ ( G , S ) = Γ 1 [ O p ] \Gamma(G,S)=\Gamma_1[O_p] Γ ( G , S ) = Γ 1 [ O p ] , then from (4) we know that
σ ( Γ 1 [ O p ] ) = { p λ : λ ∈ σ ( Γ 1 ) } ∪ { 0 } , \sigma(\Gamma_1[O_p])=\{p\lambda:\lambda\in\sigma(\Gamma_1)\}\cup\{0\}, σ ( Γ 1 [ O p ]) = { p λ : λ ∈ σ ( Γ 1 )} ∪ { 0 } ,
This shows that all eigenvalues of Γ \Gamma Γ are multiples of p p p .
Suppose now that all of the eigenvalues of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) are multiples of p p p . Then by Theorem 8.7 , we know that ∣ S ∩ g P ∣ |S \cap gP| ∣ S ∩ g P ∣ is a multiple of p p p for all g g g . In particular, P ∩ S = ∅ P \cap S=\varnothing P ∩ S = ∅ since 1 ∉ S 1 \notin S 1 ∈ / S and for each g ∉ P g \notin P g ∈ / P , either S ∩ g P = ∅ S \cap gP=\varnothing S ∩ g P = ∅ or g P ⊂ S gP \subset S g P ⊂ S . In other words, S S S is a union of cosets of P P P . By Lemma 7.7 , we know that Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) has a false twin set of size p p p and Γ ( G , S ) ≅ Γ 1 [ O p ] \Gamma(G,S)\cong\Gamma_1[O_p] Γ ( G , S ) ≅ Γ 1 [ O p ] where Γ 1 \Gamma_1 Γ 1 is a graph on the coset G / P G/P G / P . Since P P P is normal, G / P G/P G / P is a group and Γ 1 \Gamma_1 Γ 1 is a Cayley graph on G / P G/P G / P . The proof of (2) follows similarly by considering A S ∗ A_{S^*} A S ∗ where S ∗ S^* S ∗ is the set formed by adding the identity to S S S , in which case, the matrix representation of the action of A S ∗ A_{S^*} A S ∗ on Q [ G ] \mathbb{Q}[G] Q [ G ] is A + I n A+I_n A + I n . □
:::
Example 8.10. Let G = D 4 G=D_4 G = D 4 be the dihedral group generated by r , s r,s r , s ,
D 4 = ⟨ r , s ∣ r 4 = s 2 = 1 , s r s = r − 1 ⟩ . D_4=\langle r,s\mid r^4=s^2=1,\ srs=r^{-1}\rangle. D 4 = ⟨ r , s ∣ r 4 = s 2 = 1 , sr s = r − 1 ⟩ . Let Γ = Γ ( G , S ) \Gamma=\Gamma(G,S) Γ = Γ ( G , S ) where S = { r , r 2 , r 3 , s } S=\{r,r^2,r^3,s\} S = { r , r 2 , r 3 , s } . Then spec ( Γ ) = { 4 ( 1 ) , 2 ( 1 ) , 0 ( 3 ) , ( − 2 ) ( 3 ) } \operatorname{spec}(\Gamma)=\{4^{(1)},2^{(1)},0^{(3)},(-2)^{(3)}\} spec ( Γ ) = { 4 ( 1 ) , 2 ( 1 ) , 0 ( 3 ) , ( − 2 ) ( 3 ) } . As G G G is a 2 2 2 -group, it is its own 2 2 2 -Sylow group. Since ∣ S ∣ |S| ∣ S ∣ is even, Theorem 8.7 (1) guarantees that all eigenvalues of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) are even. However, one verifies that Γ \Gamma Γ has no twin set of size 2 or 4.
Finally, we deal with the case where G G G is a p p p -group. In this case, G G G is its own p p p -Sylow subgroup and we can remove the normality condition on Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) .
Corollary 8.11. Let p p p be a prime and G G G be a finite p p p -group. If Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is integral, then every eigenvalue λ \lambda λ of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) satisfies λ ≡ ∣ S ∣ ( m o d p ) \lambda\equiv|S| \pmod p λ ≡ ∣ S ∣ ( mod p ) . In particular, all eigenvalues of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) are divisible by p p p if and only if ∣ S ∣ |S| ∣ S ∣ is divisible by p p p .
Proof. We modify the proof for Theorem 8.7 . Let A A A be the adjacency matrix of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) and let A S = ∑ s ∈ S s ∈ Z [ G ] A_S=\sum_{s\in S}s\in\mathbb{Z}[G] A S = ∑ s ∈ S s ∈ Z [ G ] . The image of A S − ∣ S ∣ 1 G A_S-|S|1_G A S − ∣ S ∣ 1 G in F p [ G ] \mathbb{F}_p[G] F p [ G ] has augmentation zero. Since G G G is a finite p p p -group, the augmentation ideal of F p [ G ] \mathbb{F}_p[G] F p [ G ] is nilpotent. It follows that A − ∣ S ∣ I A-|S|I A − ∣ S ∣ I is nilpotent modulo p p p , and hence f A ( x ) ≡ ( x − ∣ S ∣ ) ∣ G ∣ ( m o d p ) f_A(x)\equiv(x-|S|)^{|G|}\pmod p f A ( x ) ≡ ( x − ∣ S ∣ ) ∣ G ∣ ( mod p ) . Since Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) is integral, we have f A ( x ) = ∏ i = 1 ∣ G ∣ ( x − λ i ) f_A(x)=\prod_{i=1}^{|G|}(x-\lambda_i) f A ( x ) = ∏ i = 1 ∣ G ∣ ( x − λ i ) where λ 1 , … , λ ∣ G ∣ \lambda_1,\ldots,\lambda_{|G|} λ 1 , … , λ ∣ G ∣ are the eigenvalues of Γ ( G , S ) \Gamma(G,S) Γ ( G , S ) . Therefore, λ i ≡ ∣ S ∣ ( m o d p ) \lambda_i\equiv|S|\pmod p λ i ≡ ∣ S ∣ ( mod p ) for every i i i . The second statement follows immediately.
Future work
In this work, we investigated sedentariness in walk-regular graphs and Cayley graphs. We imported tools from algebraic number theory to characterize sedentariness in integral walk-regular graphs in terms of their necklace polynomials. As an application, we showed that an integral Cayley graph of odd order is sedentary. Under mild assumptions, we also characterized integral normal Cayley graphs whose every eigenvalue is divisible by a prime p p p . To inspire future work on this topic, we pose the following problems.
In [4 ] , PST was characterized in integral Cayley graphs over Z n \mathbb{Z}_n Z n (also called integral circulant graphs or ICGs). By Theorem 6.3 , ICGs with an odd number of vertices are sedentary. It would be interesting to characterize sedentariness in ICGs with an even number of vertices.
For sedentary vertex-transitive graphs with twins, we were able to provide a bound on their sedentariness whenever condition (1) or (2) of Theorem 7.10 holds. However, if condition (3) or (4) of Theorem 7.10 holds, then we currently do not have a bound for sedentariness. In this case, [24 Corollary 3.14] implies that the twins are strongly cospectral. In general, it would be interesting to find a bound for sedentary twins that admit strong cospectrality.
We provided sedentary families of direct products of complete graphs. Our computations reveal that the Cartesian product and the direct product of the same set of complete graphs are either both sedentary, or both not sedentary. Is it the case that the Cartesian product of complete graphs is sedentary if and only if their direct product is?
Finally, Theorem 8.7 raises an interesting question: can we classify integral Cayley graphs whose eigenvalues have equal p p p -adic valuation, for some fixed prime number p p p ? Additionally, is there a result analogous to Theorem 8.7 for powers of p p p ?
AI Usage Declaration We acknowledge the use of ChatGPT 5.6 in developing the proof of Proposition 5.15 and checking our examples. AI tools were not used to draft the manuscript. All formal statements, arguments, and proofs in the manuscript were written and checked by the authors, who take full responsibility for the accuracy and integrity of the article.
Acknowledgments. KM is supported by NSERC Discovery Grant RGPIN-2025-04101. HM is supported by the Pacific Institute for the Mathematical Sciences. TTN is supported by an AMS-Simons Travel Grant. Parts of this work were done while TTN was visiting faculty at Argonne National Lab. He thanks Argonne for their hospitality.
References
Department of Mathematics and Statistics, University of Regina, SK, Canada S4S 0A2 Email address: karen.meagher@uregina.ca
Department of Mathematics and Statistics, University of Regina, SK, Canada S4S 0A2 Email address: hermie.monterde@uregina.ca
Department of Mathematics, Elmhurst University Email address: tung.nguyen@elmhurst.edu