# Some Algebraic Properties of a Class of Integral Graphs Determined by Their Spectrum

Authors: Jia-Bao Liu; S. Morteza Mirafzal; Ali Zafari
Journal: Journal of Mathematics
 (2021)

---

## Abstract

LetΓ=V,E be a graph. If all the eigenvalues of the adjacency matrix of the graph Γ are integers, then we say that Γ is an integral graph. A graph Γ is determined by its spectrum if every graph cospectral to it is in fact isomorphic to it. In this paper, we investigate some algebraic properties of the Cayley graph Γ=Cayℤn,S, where n=pm (p is a prime integer and m∈ℕ) and S=a∈ℤn|a,n=1. First, we show that Γ is an integral graph. Also, we determine the automorphism group of Γ. Moreover, we show that Γ and Kv▽Γ are determined by their spectrum.


---

## Body

## 1. Introduction

The graphs in this paper are simple, undirected, and connected. We always assume thatΓ¯ denotes the complement graph of Γ. The eigenvalues of a graph Γ are the eigenvalues of the adjacency matrix of Γ. The spectrum of Γ is the list of the eigenvalues of the adjacency matrix of Γ together with their multiplicities, and it is denoted by SpecΓ; see [1]. If all the eigenvalues of the adjacency matrix of the graph Γ are integers, then we say that Γ is an integral graph. The notion of integral graphs was first introduced by Harary and Schwenk in 1974; see [2]. In general, the problem of characterizing integral graphs seems to be very difficult. There are good surveys in this area; see [3]. For more results depending on the integral graphs and their applications in engineering networks, see [4–6]. For any vertex v of a connected graph Γ, we denote the set of vertices of Γ at distance r from Γ by Γrv. Then, we have(1)Γrv=u∈VΓ|du,v=r,where du,v denotes the distance in Γ between the vertices u and v and r is a nonnegative integer not exceeding d, the diameter of Γ. It is clear that Γ0v=v, and VΓ is partitioned into the disjoint subsets Γ0v,…,Γdv, 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, we have Γr+1v∩Γ1u=br, 0≤r≤d−1, and Γr−1v∩Γ1u=cr1≤r≤d. The intersection numbers cr,br, and ar satisfy ar=k−br−cr0≤r≤d, where ar is the number of neighbours of u in Γrv. Let G be a finite group and let H be a subset of G such that it is closed under taking inverses and does not contain the identity. A Cayley graph Γ=CayG,H is the graph whose vertex set and edge set are defined as follows:(2)VΓ=G;EΓ=x,y|x−1y∈H.It is well known that ifΓ is a distance regular graph with valency k, diameter d, adjacency matrix A, and intersection array(3)b0,b1,…,bd−1;c1,c2,…,cd,then the tridiagonal d+1×d+1 matrix,(4)B=a0b000…c1a1b10…0c2a2b2…cd−2ad−2bd−20…0cd−1ad−1bd−1…00cdad,determines all the eigenvalues of Γ [7]. Note that the concept of distance regular graphs dates back to the 1960s. They were defined by Biggs; see [8]; and their basic theory was developed by him and others. Distance regular graphs of diameter 2 are just the connected strongly regular graphs. The theory of distance regular graphs has connections to many parts of graph theory such as design theory, coding theory, geometry, and group theory. Two graphs with the same spectrum are called cospectral. It is not hard to see that the spectrum of a graph does not determine its isomorphism class. The authors in [9] proposed the following question: which graphs are determined by their spectrum? It seems hard to prove a graph to be determined by its spectrum. Up to now, only a few classes of graphs are proved to be determined by their spectrum, such as the path Pn, the complete graph Kn and the cycle Cn, graph Zn, and their complements; see [10–12]. For a graph Γ, let AΓ and LΓ=DΓ−AΓ be, respectively, the adjacency matrix and Laplacian matrix of Γ, where DΓ is the diagonal matrix of vertex degrees with d1,d2,…,dn as diagonal entries. Laplacian spectra and their applications are involved in diverse theoretical problems on complex networks [13, 14]. Many results have been devoted to studying Laplacian spectrum for complex networks [15, 16]. Calculating the Laplacian spectrum of networks has many applications in lots of aspects, such as the topological structures and dynamical processes [17]. Algebraic properties of various classes of Cayley graphs have been studied by various authors; see [18, 19]. In this paper, we want to study some algebraic properties of a class of Cayley graphs constructed on the cyclic additive group Zn, denoted by Γ=Cayℤn,S, where n=pm (p is a prime integer and m∈ℕ) and S=a∈ℤn|a,n=1. It is easy to check that S is an inverse closed subset in the group Zn and 0∉S. Thus, Γ is a simple graph. This class of graphs is a special subclass of graphs, which are investigated from some other aspects by Basić and Ilić [20]. Using the theory of distance regular graphs, we show that the adjacency spectrum of Γ is n−pm−1,0n−p,−pm−1p−1, where the superscripts give the multiplicities of eigenvalues with multiplicity greater than one. Finally, we show that any graph cospectral with the multicone graph Kv▽Γ is determined by its adjacency spectrum as well as its Laplacian spectrum, where Kv is the complete graph on v vertices.


## 2. Definitions and Preliminaries

Definition 1.
(see [7, 21]). Let Γ be a graph with automorphism group AutΓ. We say that Γ is a vertex transitive graph if, for all vertices x,y of Γ, there is an automorphism θ in AutΓ satisfying θx=y. Also, we say that Γ is distance transitive graph if, for all vertices u,v,x,y of Γ such that du,v=dx,y, there is an automorphism θ in AutΓ satisfying θu=x and θv=y.Theorem 1.
(see [22]). Let Γ be a graph such that it contains k components Γ1,…,Γk. If, for any i∈I=1,…,k, we have Γi≅Γ1, then AutΓ≅AutΓ1wrISymk, where the wreath product is defined.Definition 2.
(see [23]). Let Γ1∪Γ2 denote the disjoint union of graphs Γ1 and Γ2. The join Γ1▽Γ2 is the graph obtained from Γ1∪Γ2 by joining every vertex of Γ1 with every vertex of Γ2. A multicone graph is defined to be the join of a clique and a regular graph.Theorem 2.
(see [9]). If Γ is a distance regular graph with diameter d and girth g satisfying one of the following properties, then every graph cospectral with Γ is also distance regular, with the same parameters as Γ:(i)
g≥2d−1(ii)
g≥2d−2 and Γ is bipartiteProposition 1.
(see [9]). For regular graphs, being DS (or not DS) is equivalent for the adjacency matrix, the adjacency matrix of the complement, and the Laplacian matrix.Proposition 2 (see [9]).
The following graph and its complement, which have at most four eigenvalues, are regularDS graphs:(i)
The disjoint union ofk copies of a strongly regular DS graph.Theorem 3.
(see [24]). Let Γ1 and Γ2 be two graphs with the Laplacian spectrum λ1≥λ2≥⋯≥λn and μ1≥μ2≥⋯≥μm, respectively. Then, the Laplacian spectrum of Γ1▽Γ2 is n+m,m+λ1,m+λ2,…,m+λn−1,n+μ1,n+μ2,…,n+μm−1,0.Theorem 4.
(see [1]). Let Γ be a graph on n vertices. Then, n is a Laplacian eigenvalue of Γ if and only if Γ is the join of two graphs.Lemma 1.
(see [1]). A connected graph Γ has exactly one positive eigenvalue if and only if it is a complete multipartite graph.


## 3. Main Results

Theorem 5.
LetΓ=Cayℤn,S be the Cayley graph on the cyclic group Zn, where n=pm (p is a prime integer and m∈ℕ) and S=a∈ℤn|a,n=1. Then,(5)AutΓ≅Sympm−1wrISymp,where I=1,2,…,p.Proof.
LetVΓ=1,…,n be the vertex set of Γ. Note that if m=1, then the result immediately follows. Because, in this case, Γ≅Kp, where Kp is the complete graph on p vertices, in the sequel, we assume that m≥2. Let T=p=kp|0≤k≤pm−1−1 be the subgroup of the group Zn of order pm−1. It is clear that T and every coset of T represent an independent set in the graph Γ. In fact, if T+a is a coset of T in the group Zn such that T∩T+a=∅, then a and p are coprime and hence we have a∈S. It follows that every coset of T is a clique of order pm−1 in the complement of the graph Γ. Thus, Γ¯ contains p disjoint components Γ1,Γ2,…,Γp such that Γi≅Kpm−1 (1≤i≤p), where Kpm−1 is the complete graph on pm−1 vertices. It follows that Γ¯≅pKpm−1. Hence, by Theorem 1, AutΓ¯≅AutKpm−1wrISymp=Sympm−1wrISymp. On the other hand, it is well known that, for any graph Γ, AutΓ=AutΓ¯; see [1].Proposition 3.
LetΓ=Cayℤn,S be the Cayley graph on the cyclic group Zn, where n=pm (p is a prime integer and m∈ℕ) and S=a∈ℤn|a,n=1. Then Γ is a distance transitive graph.Proof.
Suppose thatu,v,x,y are vertices of Γ such that du,v=dx,y=r, where r is a nonnegative integer not exceeding d, the diameter of Γ. So du,v=dx,y=1 or 2, since we now have the diameter of Γ as d=2. In the following cases, we show that Γ is a distance transitive graph.Case 1. Ifdu,v=dx,y=2, then u−1v∉S and x−1y∉S. Therefore, two vertices u and v are adjacent in the complement Γ¯ of Γ; also two vertices x and y are adjacent in the complement Γ¯ of Γ. By Theorem 5, we know that Γ¯ contains p components Γ1,Γ2,…,Γp such that, for any i∈1,2,…,p, Γi≅Kpm−1. Therefore, Γ¯≅pKpm−1. If u=x, then u,v,y lie in a clique of graph Γ¯, and hence we may assume that θ=vy∈AutΓ¯=AutΓ, so θu=x and θv=y. If u≠x and v≠y, then u,v lie in a clique of graph Γ¯, say Γi; also x,y lie in a clique of graph Γ¯, say Γj, where Γi≠Γj or Γi=Γj. Hence, we may assume that θ=uxvy∈AutΓ¯=AutΓ. Thus, θu=x and θv=y.Case 2. Ifdu,v=dx,y=1, then we can show that there is an automorphism θ in AutΓ such that θu=x and θv=y.Proposition 4.
LetΓ=Cayℤn,S be the Cayley graph on the cyclic group Zn, where n=pm (p is a prime integer and m∈ℕ) and S=a∈ℤn|a,n=1. Then Γ is an integral graph.Proof.
It is well known that ifΓ is a distance transitive graph, then Γ is also distance regular; see [21]. Now, let VΓ=1,2,…,n be the vertex set of Γ. Consider the vertex v=n in VΓ; then Γ0v=n, Γ1v=a∈VΓ|a,n=1, and Γ2v=a∈VΓ|a,n≠1. Let u be the vertex in VΓ such that du,v=0; then u=v=n and Γ1v∩Γ1u=n−pm−1. Hence, b0=n−pm−1, and, by definition of distance regularity of graph, we have a0=n−pm−1−b0=0. Also, if u in VΓ and du,v=1, then two vertices u,v are adjacent in Γ, so Γ0v∩Γ1u=1, and Γ2v∩Γ1u=pm−1−1. Hence, c1=1, b1=pm−1−1, and a1=n−pm−1−b1−c1=n−2pm−1. Finally, if u in VΓ and du,v=2, then two vertices u,v are not adjacent in Γ, so Γ1v∩Γ1u=n−pm−1; hence, c2=n−pm−1 and a2=n−pm−1−n−pm−1=0. Thus, the intersection array of Γ is n−pm−1,pm−1−1;1,n−pm−1. Therefore, the tridiagonal 3×3 matrix,(6)a0b00c1a1b10c2a2=0n−pm−101n−2pm−1pm−1−10n−pm−10,determines all the eigenvalues of Γ. It is clear that all the eigenvalues of Γ are n−pm−1,0,−pm−1, and their multiplicities are 1,n−p,p−1, respectively. Thus, Γ is an integral graph.Corollary 1.
LetΓ=Cayℤn,S be the Cayley graph on the cyclic group Zn, where n=pm (p is a prime integer and m∈ℕ) and S=a∈ℤn|a,n=1. Then the adjacency spectrum of Γ is n−pm−1,0n−p,−pm−1p−1.Theorem 6.
LetΓ=Cayℤn,S be the Cayley graph on the cyclic group Zn, where n=pm (p is a prime integer and m∈ℕ) and S=a∈ℤn|a,n=1. Then Γ is a DS graph with respect to its adjacency spectrum.Proof.
We know that ifp is even prime integer, then Γ is isomorphic to the bipartite graph Kpm−1,pm−1, and hence the result immediately follows.
Now, letp be an odd prime integer; then, Γ is not bipartite graph. In particular, g≥2d−1, because the diameter of Γ is 2 and the girth of Γ is 3. Hence, by Theorem 2, every graph cospectral with Γ is also distance regular, with the same parameters as Γ. Because by Proposition 3 we know that Γ is a distance regular graph, Γ is a DS graph with respect to its adjacency spectra. Because, by Proposition 2, Γ¯ contains disjoint union of p copies of the strongly regular DS graph Kpm−1 in addition to the graph Γ and its complement, which have at most four eigenvalues.Proposition 5.
LetΠ be a graph cospectral with the multicone graph Kv▽Γ with respect to its adjacency matrix spectrum, where Γ=Cayℤn,S, which is defined as before. Then Π is a bidegreed graph. Also,(7)SpecΠ=0n−p,−pm−1p−1,−1v−1,M+M2+4N2,M−M2+4N2,where M=v−1+pm−pm−1 and N=pm+pm−1v−pm−1.Proof.
We can deduce the following from Theorem 2.1.8 in [25] and Theorem 2.1 in [26].Theorem 7.
Consider the multicone graphKv▽Γ, where Γ=Cayℤn,S, which is defined as before. Then Kv▽Γ is DS with respect to its adjacency matrix spectrum.Proof.
In the following, we proceed by induction on the number of vertices inKv. Let Kv have one vertex and let Π be a graph cospectral with the multicone graph K1▽Γ with respect to its adjacency matrix spectrum. By Proposition 5, it is easy to see that Π has one vertex of degree pm, say j. Hence, if SpecΠ−j=SpecΓ, then Π−j≅Γ. Because, by Theorem 6, we know that Γ is DS graph with respect to its adjacency matrix spectrum, Π≅K1▽Γ. We assume inductively that this claim holds for Kv; that is, if Π1 is a graph cospectral with the multicone graph Kv▽Γ with respect to its adjacency matrix spectrum, then Π1≅Kv▽Γ. We show that the claim is true for Kv+1; that is, if Π is a graph cospectral with the multicone graph Kv+1▽Γ with respect to its adjacency matrix spectrum, then Π≅Kv+1▽Γ. It is obvious that Π has one vertex and pm+v edges more than Π1. On the other hand, by Proposition 5, we know that Π1 has v vertices of degree pm+v−1 and pm vertices of degree pm−pm−1+v, and also Π has v+1 vertices of degree pm+v and pm vertices of degree pm−pm−1+v+1. So, we must have Π≅K1▽Π1. Now, by assuming induction, we conclude that Π≅Kv+1▽Γ and complete the proof.Theorem 8.
Consider the complementKv▽Γ¯ of multicone graph Kv▽Γ with respect to its adjacency spectrum, where Γ=Cayℤn,S, which is defined as before. Then, Kv▽Γ¯ is a DS graph.Proof.
By Theorem5, we know that Γ¯ contains p components Γ1,Γ2,…,Γp such that Γi≅Kpm−1 (1≤i≤p). So Γ¯≅pKpm−1. In addition, the adjacency matrix spectrum of Γ¯ is(8)pm−1−1p,−1pm−p.
Also, the adjacency matrix spectrum ofKv¯ is 0v. Thus, the adjacency matrix spectrum of Γ¯∪Kv¯ is(9)pm−1−1p,−1pm−p,0v.
On the other hand, it is not hard to see thatΓ¯∪Kv¯≅Kv▽Γ¯. Let Π be a graph cospectral with the complement Kv▽Γ¯ of multicone graph Kv▽Γ with respect to its adjacency spectrum; then,(10)SpecΠ=SpecKv▽Γ¯=pm−1−1p,−1pm−p,0v.
It is easy to prove thatΠ cannot be regular, since regularity of a graph can be determined by its spectrum. Also, we show that Π is disconnected graph. Suppose to the contrary that Π is connected; hence, by Lemma 1, Π is complete multipartite graph, contradicting the adjacency spectrum of Π. Thus, Π is disconnected graph. Therefore, we conclude that Kv▽Γ¯ is DS with respect to its adjacency spectrum.Proposition 6.
Consider the multicone graphKv▽Γ, where Γ=Cayℤn,S, which is defined as before. Then Kv▽Γ is DS with respect to its Laplacian spectrum.Proof.
By Theorem3, the Laplacian matrix spectrum of Kv▽Γ is(11)n+vp+v−1,n+v−pm−1n−p,0.
We proceed by induction on the number of vertices inKv. If v=1, there is nothing to prove. We assume inductively that this claim holds for Kv; that is, if SpecLΠ1=SpecLKv▽Γ, then Π1≅Kv▽Γ, where Π1 is a graph cospectral with the multicone graph Kv▽Γ with respect to its Laplacian spectrum. We show that the claim is true for Kv+1; that is, if(12)SpecLΠ=SpecLKv+1▽Γ=n+v+1p+v,n+v+1−pm−1n−p,0,then Π≅Kv+1▽Γ, where Π is a graph cospectral with the multicone graph Kv+1▽Γ with respect to its Laplacian spectrum. By Theorem 4, we know that Π1 and Π are join of two graphs, because n+v and n+v+1 are eigenvalues of Π1 and Π, respectively. In addition, Π has one vertex of degree n+v more than Π1, say j; hence, SpecLΠ−j≅SpecLKv▽Γ, and, by assuming induction, Π−j≅Kv▽Γ. Thus, it can be concluded that Π≅Kv+1▽Γ.


## 4. Conclusion

In this paper, we computed the adjacency spectrum of a class of integral graphs, denoted byΓ=Cayℤn,S, where n=pm (p is a prime integer and m∈ℕ) and S=a∈ℤn|a,n=1. Indeed, by using the theory of distance regular graphs, it is shown that the adjacency spectrum of Γ is n−pm−1,0n−p,−pm−1p−1, where the superscripts give the multiplicities of eigenvalues with multiplicity greater than one. Moreover, it is shown that the Cayley graph Γ and Kv▽Γ are determined by their spectrum. Note that this class of graphs is a special subclass of integral circulants, and hence clearly not only is this class of graphs mathematically applicable, but also it is used in the design of engineering networks.



---

*Source: 6632206-2021-02-17.xml*