Integral pentavalent Cayley graphs on abelian or dihedral groups

Abstract

A graph is called integral, if all of its eigenvalues are integers. In this paper, we give some results about integral pentavalent Cayley graphs on abelian or dihedral groups.

1 Introduction

We say that a graph is integral if all the eigenvalues of its adjacency matrix are integers. The notion of integral graphs was first introduced by Harary and Schwenk [8]. Bussemaker and Cvetković [5] proved that there are exactly 13 connected cubic integral graphs. The same result was indepedently proved by Schwenk [12] who unlike the effort in Bussemaker and Cvetković [5] avoids the use of computer search to examine all the possibilities. In [3] it is shown that the total number of matrices of integral graphs with n vertices is less than or equal to $2^{\frac {n(n-1)}{2}-\frac {n}{400}}$ for a sufficiently large n.

Stevanović [14] determined all connected 4-regular integral graphs avoiding ±3 in the spectrum. Sander [11] proved that Sudoku graphs are integral. It is known that the size of a connected k-regular graph with diameter d is bounded above by $\frac {k(k-1)^{d}-2}{k-2}$ (see, for example, [7]). In [6], it is noted that if the graph is integral then d≤2k because there are at most 2k+1 distinct eigenvalues. Consequently, the upper bound of the size of a connected k-regular integral graph is

$$\begin{array}{@{}rcl@{}} n\leq \frac{k(k-1)^{2k}-2}{k-2}. \end{array} $$

Let G be a non-trivial group, S⊆G−{1} and S = S ⁻¹={s ⁻¹∣s∈S}. The Cayley graph of G denoted by Cay(G,S) is a graph with vertex set G and two vertices a and b are adjacent if a b ⁻¹∈S. If S generates G then Cay(G,S) is connected. A Cayley graph is simple and vertex transitive. Let G be a group. An element g∈G is said to be an involution, if its order is 2. The main question that we are concerned here is the following: Which Cayley graphs are integral?

It is clear that if S = G−{1}, then Cay(G,S) is the complete graph with |G| vertices and so it is integral. Klotz and Sander [10] showed that all nonzero eigenvalues of $\text {Cay}(\mathbb {Z}_{n}, U_{n})$ are integers dividing the value φ(n) of the Euler totient function, where $\mathbb {Z}_{n}$ is the cyclic group of order n and U _n is the subset of all elements of $\mathbb {Z}_{n}$ of order n. So [13] characterized integral graphs among circulant graphs. Abdollahi and Vatandoost [1; 2], determined integral cubic and tetravalent Cayley graphs on abelian groups. By using a result of Babai [4] which presented the spectrum of a Cayley graph in terms of irreducible characters of the underlying group, we give some results on integral pentavalent Cayley graphs on abelian or dihedral groups.

2 Preliminaries

In this section we give some results which will be used in the next section.

PROPOSITION 2.1

Let Aut(G) denote the automorphism group of G. Also let α∈Aut(G). Then Cay(G,S) is isomorphic to Cay(G,S ^α ).

Proof.

It is easy to see that the map ψ:g↦g ^α is an isomorphism between two Cayley graphs. □

Proposition 2.1 ([4]).

Let G be a finite group of order n whose irreducible characters (over $\mathbb {C}$ ) are χ ₁ ,…,χ _h with respective degrees n ₁ ,…n _h . Then the spectrum of the Cayley graph Cay(G,S) can be arranged as Λ={λ _ijk ∣i=1,…,h;j;k=1,…,n _i } such that $\lambda _{ij1}=\cdots =\lambda _{ijn_{i}}$ (this common value will be denoted by λ _ij ) , and

$$\begin{array}{@{}rcl@{}} \lambda_{i1}^{t}+\cdots+\lambda_{in_{i}}^{t}=\sum\limits_{s_{1},{\ldots} ,s_{t} \in S}\chi_{i}\left( {\prod}_{l=1}^{t} s_{l}\right) \end{array} $$

(1)

for any natural number t.

Proposition 2.2 ([9]).

Let C _n be the cyclic group generated by a of order n. Then the irreducible characters of C _n are ρ _j (a ^k )=ω ^jk , where j,k=0,1,…,n−1.

Proposition 2.3 ([9]).

Let $G=C_{n_{1}}\times \cdots \times C_{n_{r}}$ and $C_{n_{i}}=\langle a_{i} \rangle ,$ so that for any i,j∈{1,…,r},(n _i ,n _j )≠1. If $\omega _{t}=e^{\frac {2\pi i}{n_{t}}},$ then n ₁ …n _r irreducible characters of G are

$$\begin{array}{@{}rcl@{}} \rho_{l_{1}{\ldots} l_{r}}(a_{1}^{k_{1}},\ldots, a_{r}^{k_{r}})=\omega_{1}^{l_{1}k_{1}}\omega_{2}^{l_{2}k_{2}}{\ldots} \omega_{r}^{l_{r}k_{r}} \end{array} $$

where l _i =0,1,…,n _i −1 and i=1,2,…,r.

Proposition 2.4 ([1]).

Let G=〈S〉 be a group ,|G|=n,|S|=2,1∉S=S ⁻¹ . Then Cay(G,S) is an integral graph if and only if n∈{3,4,6}.

Proposition 2.5 ([1]).

Let G be the cyclic group 〈a〉,|G|=n>3 and let S be a generating set of G such that |S|=3,S=S ⁻¹ and 1∉S. Then Cay(G,S) is an integral graph if and only if n∈{4,6}.

3 Results

Lemma 3.1.

Let G ₁ and G ₂ be two non-trivial abelian groups and G=G ₁ ×G ₂ such that X=Cay(G,S) is integral and G=〈S〉, where |S|=5, S=S ⁻¹ and 1∉S. Let S ₁ ={s ₁ ∣(s ₁ ,g ₂ )∈S,g ₂ ∈G ₂ }−{1}. Then Cay(G ₁ ,S ₁ ) is a connected integral graph.

Proof

Let χ ₀ and ρ ₀ be the trivial irreducible characters of G ₁ and G ₂ , respectively. Let λ _i0 and λ _i be the eigenvalues of Cay(G,S) and Cay(G ₁ ,S ₁ ) corresponding to irreducible characters of χ _i ×ρ ₀ and χ _i , respectively. We have |S ₁ |∈{1,2,3,4,5}. If |S ₁ |=1, then |G ₁ |=2 and so Cay(G ₁ ,S ₁ ) is the complete graph K ₂ with two vertices which is an integral graph. By Proposition 2.2,

$$\begin{array}{@{}rcl@{}} \lambda_{io}=\sum\limits_{(g_{1},g_{2})\in S}(\chi_{i}\times \rho_{0})(g_{1}, g_{2}). \end{array} $$

We have the following cases:

Case 1.

If |S ₁|=5, then λ _i0 = λ _i . It follows that Cay(G ₁,S ₁) is integral.

Case 2.

Let |S ₁|=4 and suppose that either S={(a,x),(a ⁻¹,x ⁻¹),(b,y),(b ⁻¹,y ⁻¹),(1,z)}, where o(z)=2 or S={(a,x),(b,y),(c,z),(d,w),(1,f)}, where o(a) = o(b) = o(c) = o(d) = o(x) = o(y) = o(z) = o(w) = o(f)=2 or S={(a,x),(b,y),(c,z),(c ⁻¹,z ⁻¹),(1,f)}, where o(a) = o(b) = o(x) = o(y) = o(f)=2 or S={(a,x),(b,y),(c,z),(c,z ⁻¹),(d,w)}, where o(a) = o(b) = o(c) = o(d) = o(x) = o(y) = o(w)=2 or S={(a,x),(a ⁻¹,x ⁻¹),(b,y),(b,y ⁻¹),(c,z)}, where o(b) = o(c) = o(z)=2. Thus either λ _i0 = λ _i + χ _i (1) or λ _i0 = λ _i + χ _i (b), or λ _i0 = λ _i + χ _i (c), respectively. Since 2|χ _i (b)−χ _i (1) and 2|χ _i (c)−χ _i (1), χ _i (b) and χ _i (c) are integers and so Cay(G ₁,S ₁).

Case 3.

Now assume that |S ₁|=3. Then either S={(a,x),(a,x ⁻¹),(b,y),(b,y ⁻¹),(c,z)}, where o(a) = o(b) = o(c) = o(z)=2 or S={(a,x),(a ⁻¹,x ⁻¹),(b,y),(b,y ⁻¹),(1,z)}, where o(b) = o(z)=2 or S={(a,x),(b,y),(c,z),(c,z ⁻¹),(1,w)}, where o(a) = o(b) = o(c) = o(x) = o(y) = o(w)=2 or S={(a,x),(b,y),(c,z),(1,e),(1,f)}, where o(a) = o(b) = o(c) = o(x) = o(y) = o(z) = o(e) = o(f)=2 or S={(a,x),(a ⁻¹,x ⁻¹),(b,y),(1,e),(1,f)}, where o(b) = o(y) = o(e) = o(f)=2. Therefore either λ _i0 = λ _i + χ _i (b) + χ _i (a) or λ _i0 = λ _i + χ _i (b) + χ _i (1) or λ _i0 = λ _i + χ _i (c) + χ _i (1) or λ _i0 = λ _i + χ _i (1) + χ _i (1). So Cay(G ₁,S ₁) is integral again. We must note that S = S ⁻¹ and if the elements e and f are not involutions then again we have the same results.

Case 4.

Finally assume that |S ₁|=2. Then either S={(a,x),(a ⁻¹,x ⁻¹),(1,y),(1,z),(1,w)}, where o(y) = o(z) = o(w)=2 or S={(a,x),(b,y),(1,z),(1,w),(1,r)}, where o(a) = o(b) = o(x) = o(y) = o(z) = o(w) = o(r)=2 or S={(a,x),(b,y),(b,y ⁻¹),(1,w),(1,z)}, where o(a) = o(b) = o(x) = o(z) = o(w)=2 or S={(a,x),(a,x ⁻¹),(b,y),(b,y ⁻¹),(1,z)}, where o(a) = o(b) = o(z)=2. Therefore either λ _i0 = λ _i + χ _i (1) + χ _i (1) + χ _i (1) or λ _i0 = λ _i + χ _i (b) + χ _i (1) + χ _i (1) or λ _i0 = λ _i + χ _i (a) + χ _i (b) + χ _i (1). So Cay(G ₁,S ₁) is integral again. We must note that S = S ⁻¹ and if the elements of the form (1,t), where t∈{y,z,w,r} are not involutions then again we have the same results.

Lemma 3.2.

Let G be the cyclic group 〈a〉,|G|=n>4 and let S be a generating set of G such that |S|=5,S=S ⁻¹ and 1∉S. Then a ^n/2 ∈S. Also let a ^r ∈S and a ^t ∈S, where o(a ^r )=m>2 and o(a ^t )=n>2. Then we have one of the following cases:

• (i) (r,n)=1 or (r,n/2)=1;

• (ii) (t,n)=1 or (t,n/2)=1;

• (iii) (t,n/2,r)=1.

Proof.

Since S = S ⁻¹, then S has at least one involution. Thus n is even and a ^n/2∈S. Therefore we may assume that S={a ^r,a ^−r,a ^t,a ^−t,a ^n/2}. Suppose on the contrary that none of the above cases happen. So we may suppose that (n/2,r) = d and (n/2,t) = d ^′. Thus $\langle a^{r}, a^{t}, a^{n/2} \rangle \subseteq \langle a^{d}, a^{d^{\prime }} \rangle$ . Since (t,n/2,r)≠1, it follows that (d,d ^′) = d ^″≠1. Thus $\langle a^{d}, a^{d^{\prime }} \rangle \subseteq \langle a^{d^{\prime \prime }} \rangle \neq G$, a contradiction. □

Theorem 3.1.

Let G be a finite abelian group such that it is not cyclic and let G=〈S〉, where |S|=5, S=S ⁻¹ and 1∉S. Also let Cay(G,S) is integral. Then |G|∈{8,16,18,24,32,36,40,48,50,64,72,80,96,100,120,128,144,160,192,200,240, 288}.

Proof.

Let Cay(G,S) be integral. If all elements of S are involutions, then $G\cong \mathbb {Z}_{2}^{3}$ or $\mathbb {Z}_{2}^{4}$ or $\mathbb {Z}_{2}^{5}$. So |G|=8, 16 or 32. Otherwise $G=\mathbb {Z}_{m} \times \mathbb {Z}_{n} \times \mathbb {Z}_{2}$ or $G=\mathbb {Z}_{m} \times \mathbb {Z}_{2} \times \mathbb {Z}_{2} \times \mathbb {Z}_{2}$. First suppose that $G=\mathbb {Z}_{m} \times \mathbb {Z}_{n} \times \mathbb {Z}_{2}$. By Lemma 3.1, $\text {Cay}(\mathbb {Z}_{m}, S_{1})$ and $\text {Cay}(\mathbb {Z}_{n} \times \mathbb {Z}_{2}, S_{2})$ are integral graphs where $S_{1}=\{s_{1} \in \mathbb {Z}_{m} \mid \exists ~x \in \mathbb {Z}_{n} \times \mathbb {Z}_{2}, (s_{1},x)\in S \}-\{1\}$ and $S_{2}=\{s_{2} \in \mathbb {Z}_{n} \times \mathbb {Z}_{2} \mid \exists ~ x \in \mathbb {Z}_{m} , (x,s_{2})\in S \}-\{1\}$ . Also since $\text {Cay}(\mathbb {Z}_{n} \times \mathbb {Z}_{2}, S_{2})$ is integral it follows that $\text {Cay}(\mathbb {Z}_{n} , S_{2}^{\prime })$ is integer where $S_{2}^{\prime }=\{s_{2}^{\prime } \in \mathbb {Z}_{n} \mid \exists ~x \in \mathbb {Z}_{2}, (s_{2}^{\prime },x)\in S_{2} \}-\{1\}$.

By Lemmas 2.7 and 2.9 of [1] and Lemma 2.14, Corollary 2.16 of [2], m,n∈{3,4,5,6,8,10,12}. Since (m,n)≠1, we have |G|∈{2×9,2×16,2×18,2×24,2×25,2×32,2×36,2×40,2×48,2×50,2×60,2×64,2×72,2×80,2×96,2×100,2×120,2×144}. Now suppose that $G=\mathbb {Z}_{m} \times \mathbb {Z}_{2} \times \mathbb {Z}_{2} \times \mathbb {Z}_{2}$. By Lemma 3.1, $\text {Cay}(\mathbb {Z}_{m}, S_{1})$ is integral where m∈{3,4,5,6,8,10,12}. So |G|∈{2×2×2×3,2×2×2×4,2×2×2×5,2×2×2×6,2×2×2×8,2×2×2×10,2×2×2×12}. Now the proof is complete. □

The following results are the generalization of results obtained recently by Abdollahi and Vatandoost [1; 2].

Lemma 3.3.

Let D _2n =〈a,b∣a ⁿ =b ² = 1,(ab) ² =1〉,n=2m+1 and Cay(D _2n ,S) be connected integral graph , where S=S ⁻¹ and |S|=k. Then −k is the simple eigenvalue of Cay(D _2n ,S) if and only if all of elements of S are of order two.

Proof

Let −k be the simple eigenvalue of Cay(D _2n ,S). By Proposition 2.2 and using character table of D _2n , −k is the eigenvalue of Cay(D _2n ,S) corresponding to the irreducible character χ _m+1. So all elements of S are in conjugacy class of b. Conversely, if all the elements of S are of order two, then $S\subseteq \overline {b}$ (the bar indicates conjugacy class). By Proposition 2.2 and using the character table of D _2n , the eigenvalue of Cay(D _2n ,S) corresponding to irreducible character χ _m+1 is −k. □

Lemma 3.4.

Let D _2n =〈a,b∣a ⁿ =b ² = 1,(ab) ² =1〉, n=2m+1 and Cay(D _2n ,S) be integral , where G=〈S〉,|S|=4,S=S ⁻¹ and 1∉S. If 3∤n, then Cay(D_2n,S) is bipartite.

Proof

Let a ^r ∈S, where 1≤r≤m. Then either S={a ^r ,a ^−r ,a ^s ,a ^−s }, where 1≤r,s<n or S={a ^r ,a ^−r ,a ⁱ b,a ^j b}, where 1≤i,j≤n, 1≤r<n and i≠j. Since X is connected the former case cannot happen. So we may suppose that S={a ^r ,a ^−r ,a ⁱ b,a ^j b}. If (r,n)=1, then since n≠3 it implies that $2~{\cos }\frac {2\pi r}{n}$ is not integer. Let λ ₁₁ and λ ₁₂ be eigenvalues of Cay(D _2n ,S) corresponding to irreducible character χ ₁ . By Proposition 2.2 and using character table of D _2n , $\lambda _{11}+\lambda _{12}=4 ~\cos \frac {2\pi r}{n}$ . This contradicts the fact that Cay(D _2n ,S) is integral. Now let (r,n)≠1. Also let λ ₁₁ and λ ₁₂ be eigenvalues of Cay(D _2n ,S) corresponding to the irreducible character χ ₁ . By Proposition 2.2, $\lambda _{11}+\lambda _{12}=4 ~\cos \frac {2\pi r}{n}$ and $\lambda _{11}^{2}+\lambda _{12}^{2}=8+4 ~\cos \frac {4\pi r}{n}+4 \cos \frac {2\pi (i-j)}{n}$ . Note that λ ₁₁ and λ ₁₂ are integers. If $4 \cos \frac {2\pi r}{n}$ is not an integer we have a contradiction. So suppose that $4 \cos \frac {2\pi r}{n}$ is an integer. Thus we must have i=j, a contradiction. So $S\subseteq \overline {b}$ and hence −4 is an eigenvalue of Cay(D_2n ,S). Therefore Cay(D _2n ,S) is bipartite.

Lemma 3.5.

Let D _2n =〈a,b∣a ⁿ =b ² =1,(ab) ² =1〉,n=2m+1 and Cay(D _2n ,S) be integral , where G=〈S〉,|S|=5,S=S ⁻¹ and 1∉S. If 3∤n, then Cay(D _2n ,S) is bipartite.

Proof.

Let a ^r∈S, where 1≤r≤n. Then either S={a ^r,a ^−r,a ^s,a ^−s,a ⁱ b}, where 1≤r,s<n and 1≤i≤n or S={a ^r,a ^−r,a ⁱ b,a ^j b,a ^k b}, where 1≤r<n and 1≤i,j,k≤n. First suppose that S={a ^r,a ^−r,a ^s,a ^−s,a ⁱ b}. Since Aut (G) acts transitively on involution, by Proposition 2.1, we may suppose that S={a ^r,a ^−r,a ^s,a ^−s,b}. Since X is connected, without loss of generality, we may suppose that (r,n)=1. Thus $\cos \frac {2\pi }{n}r$ is not integral. Let λ ₁₁ and λ ₁₂ be eigenvalues of Cay(D _2n ,S) corresponding to irreducible character χ ₁. By Proposition 2.2 and using character table of D _2n , $\lambda _{11}+\lambda _{12}=4 \cos \frac {2\pi r}{n}+4 \cos \frac {2\pi s}{n}$ . First suppose that $-\cos \frac {2\pi r}{n}=\cos \frac {2\pi s}{n}$. Therefore $\cos (\pi +\frac {2\pi r}{n})=\cos \frac {2\pi s}{n}$ and so 2π s=2k π n±(n π+2π r), a contradiction. Now suppose that $-\cos \frac {2\pi r}{n}\neq \cos \frac {2\pi s}{n}$. Since $\cos \frac {2\pi }{n}r$ is not integral and λ ₁₁ + λ ₁₂ is integral, we have a contradiction. □

ᅟ Character table of D _2n , n=2m+1 odd.

Now suppose that S={a ^r,a ^−r,a ⁱ b,a ^j b,a ^k b}. If (r,n)=1, then since n ≠ 3 it implies that $2 \cos \frac {2\pi }{n}r$ is not an integer. Let λ ₁₁ and λ ₁₂ be eigenvalues of Cay(D _2n ,S) corresponding to irreducible character χ ₁. By Proposition 2.2 and using character table of D _2n , $\lambda _{11}+\lambda _{12}=4 \cos \frac {2\pi r}{n}$. This contradicts the fact that Cay(D _2n ,S) is integral. Now let (r,n)≠1. Also let λ ₁₁ and λ ₁₂ be eigenvalues of Cay(D _2n ,S) corresponding to irreducible character χ ₁. Since 3∤n, with similar arguments we have a contradiction. So $S\subseteq \overline {b}$ and hence −5 is an eigenvalue of Cay(D _2n ,S). Therefore Cay(D _2n ,S) is bipartite.