# An Interesting Property of a Class of Circulant Graphs

Authors: Seyed Morteza Mirafzal; Ali Zafari
Journal: Journal of Mathematics
 (2017)

---

## Abstract

Suppose thatΠ=Cay(Zn,Ω) and Λ=Cay(Zn,Ψm) are two Cayley graphs on the cyclic additive group Zn, where n is an even integer, m=n/2+1, Ω=t∈Zn∣tis  odd, and Ψm=Ω∪{n/2} are the inverse-closed subsets of Zn-0. In this paper, it is shown that Π is a distance-transitive graph, and, by this fact, we determine the adjacency matrix spectrum of Π. Finally, we show that if n≥8 and n/2 is an even integer, then the adjacency matrix spectrum of Λ is n/2+11, 1-n/21, 1n-4/2, -1n/2 (we write multiplicities as exponents).


---

## Body

## 1. Introduction

In this paper, graphΓ=(V,E) always means a simple connected graph with n vertices (without loops, multiple edges, and isolated vertices), where V=V(Γ) is the vertex set and E=E(Γ) is the edge set. Graph Γ is called a vertex-transitive graph, if, for any x,y∈V, there is some π in Aut(Γ), the automorphism group of Γ, such that π(x)=y. Let Γ be a graph, the complement Γ¯ of Γ is the graph whose vertex set is V(Γ) and whose edges are the pairs of nonadjacent vertices of Γ. It is well known that, for any graph Γ, Aut(Γ)=Aut(Γ¯) [1]. If Γ is a connected graph and ∂(u,v) denotes the distance in Γ between the vertices u and v, then, for any automorphism π in Aut(Γ), we have ∂(u,v)=∂(π(u),π(v)).LetΥ=γ1,…,γk+1 be a set and K be a group; then, writing Fun(Υ,K) to denote the set of all functions from Υ into K, we can turn Fun(Υ,K) into a group by defining a product: (1)fgγ=fγgγ∀f,g∈FunΥ,Kandγ∈Υ, where the product on the right is in K. Since Υ is finite then the group Fun(Υ,K) is isomorphic to Kk+1 (a direct product of k+1 copies of K) via the isomorphism f→(f(γ1),…,f(γk+1)). Let H and K be groups and suppose that H acts on the nonempty set Υ. Then, the wreath product of K by H with respect to this action is defined to be the semidirect product Fun(Υ,K)⋊H where H acts on the group Fun(Υ,K) via (2)fxγ=fγx-1∀f∈FunΥ,K,γ∈Υandx∈H. We denote this group by KwrΥH. Consider the wreath product G=KwrΥH. If K acts on a set Δ, then we can define an action of G on Δ×Υ by (3)δ,γf,h=δfγ,γh∀δ,γ∈Δ×Υ, where (f,h)∈Fun(Υ,K)⋊H=KwrΥH [2].LetG be a group and H≤G a subgroup of G and S⊆G. The Schreier coset graph on G/H generated by S is the graph Γ=Γ(G,H,S) with V(Γ)=G/H=gH∣g∈G the set of left cosets of H, and there is an edge (gH,sgH) for each coset gH and each s∈S. If S is inverse-closed, then Γ is an undirected multigraph (possibly with loops). Note that if 1G is the identity element of G, then Γ(G,1G,S)=Γ(G,S) is the Cayley graph on G generated by S. It is well known that every Cayley graph is vertex-transitive [3].LetΓ be a graph with automorphism group Aut(Γ). Say that Γ is symmetric graph if, for all vertices u,v,x,y of Γ such that u and v are adjacent, also, x and y are adjacent, and there is an automorphism π in Aut(Γ) such that π(u)=x and π(v)=y. We say that Γ is distance-transitive if, for all vertices u,v,x,y of Γ such that ∂(u,v)=∂(x,y), there is an automorphism π in Aut(Γ) satisfying π(u)=x and π(v)=y [3]. It is clear that hierarchy of the conditions is(4)distance-transitive⟹symmetric⟹vertex-transitive.Eigenvalues of an undirected graphΓ are the eigenvalues of an arbitrary adjacency matrix of Γ. Harary and Schwenk [4] defined Γ to be integral, if all of its eigenvalues are integers. For a survey of integral graphs, see [5]. In [6], the number of integral graphs on n vertices is estimated. Known characterizations of integral graphs are restricted to certain graph classes; see [7].In this paper, supposeΠ=Cay(Zn,Ω) and Λ=Cay(Zn,Ψm) are two Cayley graphs on the cyclic additive group Zn, where n is an even integer, m=n/2+1, Ω=t∈Zn∣t  is  odd, and Ψm=Ω∪{n/2} are the inverse-closed subsets of Zn-{0}. One of our goals in this paper is to obtain all eigenvalues of the Cayley graph Λ=Cay(Zn,Ψm). First, we determine the group automorphism of Π and we show that Π is a distance transitive graph; also, by this fact, we determine the adjacency matrix spectrum of Π. Finally, according to these facts, we show that if n≥8 and n/2 is an even integer, then the adjacency matrix spectrum of Λ is n/2+11,1-n/21,1n-4/2,-1n/2 (we write multiplicities as exponents).


## 2. Definitions and Preliminaries

Definition 1 (see [3, 8]).
For any vertexv of a connected graph Γ, one defines (5)Γrv=u∈VΓ∣∂u,v=r,where r is a nonnegative integer not exceeding d, the diameter of Γ. It is clear that Γ0(v)={v}, and V(Γ) is partitioned into the disjoint subsets Γ0(v),…,Γd(v), for each v in V(Γ). The graph Γ is called distance-regular with diameter d and intersection array {b0,…,bd-1;c1,…,cd}, if it is regular of valency k and, for any two vertices u and v in Γ at distance r, one has Γr+1v∩Γ1u=br, and Γr-1v∩Γ1u=cr, 0≤r≤d. The numbers cr,br, and ar, where (6)ar=k-br-cr0≤r≤d, is the number of neighbours of u in Γr(v) for ∂(u,v)=r, are called the intersection numbers of Γ. Clearly b0=k, bd=c0=0, and c1=1.Remark 2 (see [3]).
It is clear that ifΓ is distance-transitive graph, then Γ is distance-regular.Lemma 3 (see [3]).
A connected graphΓ with diameter d and automorphism group G=Aut(Γ) is distance-transitive if and only if it is vertex-transitive and the vertex-stabilizer Gv is transitive on the set Γr(v), for each r∈0,1,…,d, and v∈V(Γ).Theorem 4 (see [8]).
LetΓ be a distance-regular graph which the valency of each vertex as k, with diameter d, adjacency matrix A, and intersection array, is(7)b0,b1,…,bd-1;c1,c2,…,cd. Then, the tridiagonal (d+1)×(d+1) matrix(8)jΓ=a0b000⋯c1a1b10⋯0c2a2b2⋯cd-2ad-2bd-20⋯0cd-1ad-1bd-1⋯00cdad determines all the eigenvalues of Γ.Theorem 5 (see [9]).
LetF be a field and let R be a commutative subring of Fn×n, the set of all n×n matrices over F. Let M∈Rm×m, then detF⁡(M)=detF⁡(detR(M)).Theorem 6 (see [10]).
LetΓ be a graph such that contains k+1 components Γ1,…,Γk+1. If, for any i∈I={1,…,k+1}, Γi≅Γ1, then Aut(Γ)≅Aut(Γ1)wrISym(k+1).


### 2.1. Main Results

Proposition 7.
LetΠ=Cay(Zn,Ω) be the Cayley graph on the cyclic group Zn(n≥4), where Ω=t∈Zn∣t  is  odd is the inverse-closed subset of Zn-{0}. Then Aut(Π)≅Sym(n/2)wrISym(2), where I={1,2}.Proof.
LetV(Π)=1,…,n be the vertex set of Π. By assumption, the size of the every independent set of vertices in Π is n/2, because Π is a vertex-transitive graph and the size of every clique in graph Π is 2. Therefore, for any x∈V(Π), there is exactly n/2, y∈V(Π) such that x-1y∉Ω. Hence, if x-1y∉Ω, then two vertices x and y are adjacent in the complement Π¯ of Π, so Π¯ contains 2 components Π1,Π2 such that Π1≅Π2≅Kn/2, where Kn/2 is the complete graph of n/2 vertices. Therefore, Π¯≅2Kn/2. Hence, by Theorem 6, Aut(Π¯)≅Aut(Kn/2)wrISym(2)=Sym(n/2)wrISym(2).Proposition 8.
LetΠ=Cay(Zn,Ω) be the Cayley graph on the cyclic group Zn(n≥4), where n is an even integer and Ω=t∈Zn∣t  is  odd is the inverse-closed subset of Zn-{0}; then Π is a distance-transitive graph.Proof.
Suppose thatu,v,x,y are vertices of Π such that ∂(u,v)=∂(x,y)=r, where r is a nonnegative integer not exceeding d, the diameter of Π. So ∂(u,v)=∂(x,y)=1 or 2, since d=2.
(a) If∂(u,v)=∂(x,y)=2, then u-1v∉Ω and x-1y∉Ω. Therefore, two vertices u and v are adjacent in the complement Π¯ of Π, also two vertices x and y are adjacent in the complement Π¯ of Π. So Π¯ contains 2 components Π1,Π2 such that Π1≅Π2≅Kn/2. Therefore Π¯≅2Kn/2; hence we may assume π=(ux)(vy)∈Aut(Π¯)=Aut(Π), so π(u)=x and π(v)=y.
(b) If∂(u,v)=∂(x,y)=1, then, by Lemma 3, it is sufficient to show that vertex-stabilizer Gv is transitive on set Πr(v) for every r∈0,1,2 and every v∈V(Π), because Π is a vertex-transitive graph. In this case, let V(Π)=1,2,…,n be the vertex set of Π and G=Aut(Π). Consider the vertex v=1 in V(Π), then Π0(v)={1}, Π1(v)=t∈Zn∣t  is  even, and Π2(v)=1≠t∈Zn∣t  is  odd. Let H be the group that is generated by all elements of sets Π1(v) and Π2(v), say H=(2,4,…,n),3,5,…,n-1. It is clear that H is a subgroup of Aut(Π), so the group H is a subgroup of Gv such that transitive on the set Πr(v) for each r∈0,1,2. Note that if 1≠v∈V(Π), then, we can show that vertex-stabilizer Gv is transitive on the set Πr(v) for each r∈0,1,2, because Π is a vertex-transitive graph.Proposition 9.
LetΠ=Cay(Zn,Ω) be the Cayley graph on the cyclic group Zn(n≥4), where n is an even integer and Ω=t∈Zn∣t  is  odd is the inverse-closed subset of Zn-{0}; then Π is an integral graph.Proof.
By Remark2, it is clear that Π is distance-regular, because Π is a distance-transitive graph. Let V(Π)={1,2,…,n} be the vertex set of Π. Consider the vertex v=1 in V(Π); then Π0(v)={1}, Π1(v)=t∈Zn∣t  is  even, and Π2(v)=1≠t∈Zn∣t  is  odd. Let be u in V(Π) such that ∂(u,v)=0; then u=v=1 and Π1v∩Π1u=n/2; hence b0=n/2 and, by Definition 1, a0=n/2-b0=0. Also, if u in V(Π) and ∂(u,v)=1, then two vertices u,v are adjacent in Π, so Π0v∩Π1u=1 and Π2v∩Π1u=n/2-1; hence c1=1, b1=n/2-1, and a1=n/2-b1-c1=0. Finally, if u in V(Π) and ∂(u,v)=2, then two vertices u,v are not adjacent in Π, so Π1v∩Π1u=n/2; hence c2=n/2 and a2=n/2-c2=0. So the intersection array of Π is {n/2,n/2-1;1,n/2}. Therefore, by Theorem 4, the tridiagonal (3)×(3) matrix(9)a0b00c1a1b10c2a2=0n2010n2-10n20determines all the eigenvalues of Π. It is clear that all the eigenvalues of Π are n/2,-n/2,0, and their multiplicities are 1,1,n-2, respectively. So Π is an integral graph.Conclusion 10.
LetΠ=Cay(Zn,Ω) be the Cayley graph on the cyclic group Zn as before with the adjacency matrix M=AAAA, and characteristic polynomial ΦΠ(x) then is(10)Φ2Ax=detxIn/2-2A=x-n2x+n2xn-4/2.Proof.
It is easy to show that the adjacency matrixM=AAAA, where A is n/2×n/2 matrix; hence, by Proposition 9 and Theorem 5, (11)ΦΠx=detxIn-M=detxIn/2-A-A-AxIn/2-A=detxIn/2-A2-A2=detxIn/2-A-AdetxIn/2-A+A=detxIn/2-2AdetxIn/2=Φ2Axxn/2=x-n2x+n2xn-4/2xn/2.Proposition 11.
LetΛ=Cay(Zn,Ψm) be the Cayley graph on the cyclic group Zn as before with the adjacency matrix M^ and characteristic polynomial ΦΛ(x). If n≥8 and n/2 is an even integer, then (12)ΦΛx=x-n2+1x-1-n2x-1n-4/2x+1n/2.Proof.
It is easy to show that the adjacency matrixM^=AA+IA+IA, where A is n/2×n/2 matrix; hence, by Conclusion 10 and Theorem 5,(13)ΦΛx=detxIn-M^=detxIn/2-A-A+I-A+IxIn/2-A=detxIn/2-A2-A+I2=detxIn/2-A-A+IdetxIn/2-A+A+I=detx-1In/2-2Adetx+1In/2=Φ2Ax-1x+1n/2=x-n2+1x-1-n2x-1n-4/2x+1n/2.Conclusion 12.
LetΛ=Cay(Zn,Ψm) be the Cayley graph on the cyclic group Zn, where n is an even integer, m=n/2+1, and Ψm=Ω∪{n/2} is the inverse-closed subset of Zn-{0}. If n≥8 and n/2 is an even integer, then the adjacency matrix spectrum of Λ is n/2+11, 1-n/21, 1n-4/2, -1n/2.


## 2.1. Main Results

Proposition 7.
LetΠ=Cay(Zn,Ω) be the Cayley graph on the cyclic group Zn(n≥4), where Ω=t∈Zn∣t  is  odd is the inverse-closed subset of Zn-{0}. Then Aut(Π)≅Sym(n/2)wrISym(2), where I={1,2}.Proof.
LetV(Π)=1,…,n be the vertex set of Π. By assumption, the size of the every independent set of vertices in Π is n/2, because Π is a vertex-transitive graph and the size of every clique in graph Π is 2. Therefore, for any x∈V(Π), there is exactly n/2, y∈V(Π) such that x-1y∉Ω. Hence, if x-1y∉Ω, then two vertices x and y are adjacent in the complement Π¯ of Π, so Π¯ contains 2 components Π1,Π2 such that Π1≅Π2≅Kn/2, where Kn/2 is the complete graph of n/2 vertices. Therefore, Π¯≅2Kn/2. Hence, by Theorem 6, Aut(Π¯)≅Aut(Kn/2)wrISym(2)=Sym(n/2)wrISym(2).Proposition 8.
LetΠ=Cay(Zn,Ω) be the Cayley graph on the cyclic group Zn(n≥4), where n is an even integer and Ω=t∈Zn∣t  is  odd is the inverse-closed subset of Zn-{0}; then Π is a distance-transitive graph.Proof.
Suppose thatu,v,x,y are vertices of Π such that ∂(u,v)=∂(x,y)=r, where r is a nonnegative integer not exceeding d, the diameter of Π. So ∂(u,v)=∂(x,y)=1 or 2, since d=2.
(a) If∂(u,v)=∂(x,y)=2, then u-1v∉Ω and x-1y∉Ω. Therefore, two vertices u and v are adjacent in the complement Π¯ of Π, also two vertices x and y are adjacent in the complement Π¯ of Π. So Π¯ contains 2 components Π1,Π2 such that Π1≅Π2≅Kn/2. Therefore Π¯≅2Kn/2; hence we may assume π=(ux)(vy)∈Aut(Π¯)=Aut(Π), so π(u)=x and π(v)=y.
(b) If∂(u,v)=∂(x,y)=1, then, by Lemma 3, it is sufficient to show that vertex-stabilizer Gv is transitive on set Πr(v) for every r∈0,1,2 and every v∈V(Π), because Π is a vertex-transitive graph. In this case, let V(Π)=1,2,…,n be the vertex set of Π and G=Aut(Π). Consider the vertex v=1 in V(Π), then Π0(v)={1}, Π1(v)=t∈Zn∣t  is  even, and Π2(v)=1≠t∈Zn∣t  is  odd. Let H be the group that is generated by all elements of sets Π1(v) and Π2(v), say H=(2,4,…,n),3,5,…,n-1. It is clear that H is a subgroup of Aut(Π), so the group H is a subgroup of Gv such that transitive on the set Πr(v) for each r∈0,1,2. Note that if 1≠v∈V(Π), then, we can show that vertex-stabilizer Gv is transitive on the set Πr(v) for each r∈0,1,2, because Π is a vertex-transitive graph.Proposition 9.
LetΠ=Cay(Zn,Ω) be the Cayley graph on the cyclic group Zn(n≥4), where n is an even integer and Ω=t∈Zn∣t  is  odd is the inverse-closed subset of Zn-{0}; then Π is an integral graph.Proof.
By Remark2, it is clear that Π is distance-regular, because Π is a distance-transitive graph. Let V(Π)={1,2,…,n} be the vertex set of Π. Consider the vertex v=1 in V(Π); then Π0(v)={1}, Π1(v)=t∈Zn∣t  is  even, and Π2(v)=1≠t∈Zn∣t  is  odd. Let be u in V(Π) such that ∂(u,v)=0; then u=v=1 and Π1v∩Π1u=n/2; hence b0=n/2 and, by Definition 1, a0=n/2-b0=0. Also, if u in V(Π) and ∂(u,v)=1, then two vertices u,v are adjacent in Π, so Π0v∩Π1u=1 and Π2v∩Π1u=n/2-1; hence c1=1, b1=n/2-1, and a1=n/2-b1-c1=0. Finally, if u in V(Π) and ∂(u,v)=2, then two vertices u,v are not adjacent in Π, so Π1v∩Π1u=n/2; hence c2=n/2 and a2=n/2-c2=0. So the intersection array of Π is {n/2,n/2-1;1,n/2}. Therefore, by Theorem 4, the tridiagonal (3)×(3) matrix(9)a0b00c1a1b10c2a2=0n2010n2-10n20determines all the eigenvalues of Π. It is clear that all the eigenvalues of Π are n/2,-n/2,0, and their multiplicities are 1,1,n-2, respectively. So Π is an integral graph.Conclusion 10.
LetΠ=Cay(Zn,Ω) be the Cayley graph on the cyclic group Zn as before with the adjacency matrix M=AAAA, and characteristic polynomial ΦΠ(x) then is(10)Φ2Ax=detxIn/2-2A=x-n2x+n2xn-4/2.Proof.
It is easy to show that the adjacency matrixM=AAAA, where A is n/2×n/2 matrix; hence, by Proposition 9 and Theorem 5, (11)ΦΠx=detxIn-M=detxIn/2-A-A-AxIn/2-A=detxIn/2-A2-A2=detxIn/2-A-AdetxIn/2-A+A=detxIn/2-2AdetxIn/2=Φ2Axxn/2=x-n2x+n2xn-4/2xn/2.Proposition 11.
LetΛ=Cay(Zn,Ψm) be the Cayley graph on the cyclic group Zn as before with the adjacency matrix M^ and characteristic polynomial ΦΛ(x). If n≥8 and n/2 is an even integer, then (12)ΦΛx=x-n2+1x-1-n2x-1n-4/2x+1n/2.Proof.
It is easy to show that the adjacency matrixM^=AA+IA+IA, where A is n/2×n/2 matrix; hence, by Conclusion 10 and Theorem 5,(13)ΦΛx=detxIn-M^=detxIn/2-A-A+I-A+IxIn/2-A=detxIn/2-A2-A+I2=detxIn/2-A-A+IdetxIn/2-A+A+I=detx-1In/2-2Adetx+1In/2=Φ2Ax-1x+1n/2=x-n2+1x-1-n2x-1n-4/2x+1n/2.Conclusion 12.
LetΛ=Cay(Zn,Ψm) be the Cayley graph on the cyclic group Zn, where n is an even integer, m=n/2+1, and Ψm=Ω∪{n/2} is the inverse-closed subset of Zn-{0}. If n≥8 and n/2 is an even integer, then the adjacency matrix spectrum of Λ is n/2+11, 1-n/21, 1n-4/2, -1n/2.



---

*Source: 6454736-2017-02-27.xml*