On the spectrum of Cayley graphs
The set of eigenvalues of the adjacency matrix of a graph is called the spectrum of it. In the present paper, we introduce the spectrum of Cayley graphs of order pqr in terms of character table, where p, q, r are prime numbers. We also, stablish some properties of Cayley graphs of non-abelian group...
Збережено в:
| Дата: | 2020 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2020
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/188563 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | On the spectrum of Cayley graphs / M. Ghorbani, M. Songhori // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 2. — С. 194–206. — Бібліогр.: 24 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188563 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1885632023-03-07T01:26:49Z On the spectrum of Cayley graphs Ghorbani, M. Songhori, M. The set of eigenvalues of the adjacency matrix of a graph is called the spectrum of it. In the present paper, we introduce the spectrum of Cayley graphs of order pqr in terms of character table, where p, q, r are prime numbers. We also, stablish some properties of Cayley graphs of non-abelian groups with a normal symmetric connected subset. 2020 Article On the spectrum of Cayley graphs / M. Ghorbani, M. Songhori // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 2. — С. 194–206. — Бібліогр.: 24 назв. — англ. 1726-3255 DOI:10.12958/adm544 2010 MSC: 20D15 http://dspace.nbuv.gov.ua/handle/123456789/188563 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
The set of eigenvalues of the adjacency matrix of a graph is called the spectrum of it. In the present paper, we introduce the spectrum of Cayley graphs of order pqr in terms of character table, where p, q, r are prime numbers. We also, stablish some properties of Cayley graphs of non-abelian groups with a normal symmetric connected subset. |
| format |
Article |
| author |
Ghorbani, M. Songhori, M. |
| spellingShingle |
Ghorbani, M. Songhori, M. On the spectrum of Cayley graphs Algebra and Discrete Mathematics |
| author_facet |
Ghorbani, M. Songhori, M. |
| author_sort |
Ghorbani, M. |
| title |
On the spectrum of Cayley graphs |
| title_short |
On the spectrum of Cayley graphs |
| title_full |
On the spectrum of Cayley graphs |
| title_fullStr |
On the spectrum of Cayley graphs |
| title_full_unstemmed |
On the spectrum of Cayley graphs |
| title_sort |
on the spectrum of cayley graphs |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2020 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188563 |
| citation_txt |
On the spectrum of Cayley graphs / M. Ghorbani, M. Songhori // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 2. — С. 194–206. — Бібліогр.: 24 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT ghorbanim onthespectrumofcayleygraphs AT songhorim onthespectrumofcayleygraphs |
| first_indexed |
2025-07-16T10:40:16Z |
| last_indexed |
2025-07-16T10:40:16Z |
| _version_ |
1837799746626912256 |
| fulltext |
© Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 30 (2020). Number 2, pp. 194–206
DOI:10.12958/adm544
On the spectrum of Cayley graphs
M. Ghorbani and M. Songhori
Communicated by I. Ya. Subbotin
Abstract. The set of eigenvalues of the adjacency matrix
of a graph is called the spectrum of it. In the present paper, we
introduce the spectrum of Cayley graphs of order pqr in terms of
character table, where p, q, r are prime numbers. We also, stablish
some properties of Cayley graphs of non-abelian groups with a
normal symmetric connected subset.
Introduction
By investigating Cayley graphs, even more detailed information about
a group can be obtained. In this paper, we study the spectral properties
of Cayley graphs via the character table of underlying group.
Computing the spectrum of Cayley graphs was started by a paper
of Babai [2] in 1979 and recently, this exciting research topic is re-
ceived increasing attention by mathematician, see for example [4,6,19,22].
Ghorbani and Nowroozi in a series of articles computed the spectrum
of normal and normal edge-transitive Cayley graphs of order n where
n ∈ {p3, p2q, pqr, 2pq} and p, q, r are prime numbers, see [9, 11–15]. But
in general the spectrum of Cayley graphs of these groups is still an open
problem. Here, we compute the spectrum of such Cayley graphs by means
of character table. We also compute the spectrum of Cayley graphs of
non-abelian groups by constructing the circulant matrices, see [9].
2010 MSC: 20D15.
Key words and phrases: Cayley graphs, symmetric set, semi-direct product,
characteristic polynomial.
https://doi.org/10.12958/adm544
M. Ghorbani, M. Songhori 195
In the next section, we give the necessary definitions and some prelim-
inary results. In section three, we stablish a formula for computing the
spectra of normal Cayley graphs. Finally, in section four, we compute the
spectrum of Cayley graphs of order pqr, in general. Here, our notation is
standard and mainly taken from the standard books such as [16].
1. Definitions and preliminaries
Here, we introduce some basic notation and terminology used through-
out the paper. All graphs considered here are finite and simple. A simple
graph is a graph Γ without loops and multiple edges. The vertex set
and the edge set of graph Γ are denoted by V (Γ) and E(Γ), respectively.
When two vertices u and v are endpoints of an edge, we say that they are
adjacent and write u ∼ v to indicate this. The adjacency matrix A is an
n× n matrix whose xy-th entry is 1 if xy ∈ E and zero otherwise.
For given graphs Γ1 and Γ2 their Cartesian product Γ1 � Γ2 is defined
as the graph on the vertex set V (Γ1) × V (Γ2), where two vertices u =
(u1, u2) and v = (v1, v2) are adjacent if and only if either ([u1 = v1
and u2v2 ∈ E(Γ2)]) or ([u2 = v2 and u1v1 ∈ E(Γ1)]). It is well-known
that A(Γ1 � Γ2) = A(Γ1)⊗ I + I ⊗ A(Γ2), where ⊗ denotes the Tensor
(Kronecker) product see [5].
For the finite group G, the generating subset S is symmetric if 1 6∈ S
and S = S−1. The Cayley graph Γ = Cay(G,S) on G with respect to S
has the vertex set V (Γ) = G and edge set E(Γ) = {(g, sg)|g ∈ G, s ∈ S}.
By this definition the Cayley graph Cay(G,S) always is connected.
Theorem 1 ([1]). Let Γ1 = Cay(G,S1) and Γ2 = Cay(H,S2) be two
Cayley graphs. Then the Cartesian product Γ1 � Γ2 is the Cayley graph of
the direct product G×H with the generating subset (S1, 1)� (1, S2).
The characteristic polynomial χ(Γ) of graph Γ with adjacency matrix
A is defined as χ(Γ) = det(xI − A). It is a monic polynomial of degree
n. The roots of the charachteristic polynomial are eigenvalues of Γ and
form the spectrum of Γ. Since all considered graphs are undirected, the
adjacency matrix A is symmetric. Consequently, all eigenvalues are real.
Theorem 2 ([3]). Let A and B is square matrices of orders m and n,
respectively. If λ1, . . . , λm are eigenvalues of A and µ1, . . . , µn are the
eigenvalues of B, then all eigenvalues of A ⊗ B are λiµj (6 i 6 m, 1 6
j 6 n).
196 On the spectrum of Cayley graphs
It is well-known that if A is a matrix of order m with eigenvalues λi
and B is a matrix of order n with eigenvalues µj , then all eigenvalues of
aA⊗ In + bIm ⊗B are aλi + bµj , where 1 6 i 6 m and 1 6 j 6 n.
A circulant matrix is a square matrix generated from a vector such as
[a0, . . . an−1] as the first row denoted by [[a0, . . . , an−1]]. Successive rows
use the same elements as the first row but each such row is circularly
shifted by one element. All eigenvalues of this circulant matrix are λω =
∑n−1
i=0 aiω
i, where ω is an n-th root of unity.
Theorem 3 ([2]). Let (Aij , 1 6 i, j 6 l) be square matrices of order n that
have the complete set of eigenvectors {V1, . . . , Vn} with AijVk = αk
ijVk. Let
also, Bk = [αk
ij ] be square matrices of order l, each with a complete set of
eigenvectors {Uk
1 , . . . , U
k
l } satisfying BkU
k
j = βkj U
k
j for 1 6 j 6 l. Then a
complete set of eigenvectors {W1,W2, . . . ,Wnl} for the square matrix
A =
A11 A12 . . . A1l
A21 A22 . . . A2l
...
...
. . .
...
Al1 Al2 . . . All
is given by W(k−1)l+j = Uk
j ⊗ Vk, for k = 1, 2, . . . , n and j = 1, 2, . . . , l.
The corresponding eigenvalues are λ(k−1)l+j = βkj .
In continuing of this paper, we use above results to compute the
spectrum of Cayley graphs. First, we compute the spectrum of a group of
order 8n denoted by V8n with the following presentation:
V8n = 〈a, b, a2n = b4 = 1, ba = a−1b−1, b−1a = a−1b〉,
where n is an odd number. By using the relations of this group, we conclude
that this group has exactly 8n elements as follows:
{braj , 1 6 r 6 4, 1 6 j 6 2n}. (1)
It is clear that in a Cayley graph the vertex 1 correspond to identity
is adjacent with all elements of S.
Theorem 4. The adjacency matrix of the Cayley graph Γ = Cay(V8n, S)
where S = {bar, bas, b3ak} (1 6 i 6 2n− 1) is as follows:
• ai is adjacent with
{
bar−i, bas−i, b3at−i 2 | i
bat−i, b3as−i, b3ar−i 2 ∤ i
,
M. Ghorbani, M. Songhori 197
• bai is adjacent with
{
at−i, b2as−i, b2ar−i 2 | i
b2at−i, as−i, ar−i 2 ∤ i
,
• b2ai is adjacent with
{
bat−i, b3as−i, b3ar−i 2 | i
bar−i, bas−i, b3at−i 2 ∤ i
,
• b3ai is adjacent with
{
b2at−i, as−i, ar−i 2 | i
at−i, b2as−i, b2ar−i 2 ∤ i
,
Proof. The proof is straightforward.
Corollary 1. Let G be a group V8n. The adjacency matrix of the cubic
Cayley graph Γ = Cay(G,S), where S = {bar, bas, b3ak} is the following
circulant matrix (
0 A
AT 0
)
,
where A = [[0, B, 0, C]] = B⊗C +E⊗F and B,C,E, F are the following
circulant matrices:
B = [[0, . . . , 0,
r
︷︸︸︷
1 , 0, . . . , 0,
s
︷︸︸︷
1 , 0, . . . , 0]],
C = [[0, 1, 0, 0]],
E = [[0, . . . , 0,
t
︷︸︸︷
1 , 0, . . . , 0]],
F = [[0, 0, 0, 1]].
Theorem 5. Suppose ω = e
π
n
i, then
1) All eigenvalues of matrix B are λj = ω(r−1)j + ω(s−1)j in which
j = 0, . . . , 2n− 1,
2) The eigenvalues of C and F are ±i,±1,
3) The eigenvalues of E are λj = ωj where j = 0, . . . , 2n− 1.
One can apply Theorem 5 to compute all eigenvalues of Cayley graph
Γ = Cay(V8n, S). For example, in the following example, we compute all
eigenvalues on Cayley graph Cay(V24, S).
198 On the spectrum of Cayley graphs
Example 1. Consider the tetravalent Cayley graph Γ = Cay(V24, S),
where S = {ba, ba5, b3a5}. The adjacency matrix Γ is
(
0 A
AT 0
)
,
where A = [[0, B, 0, C]], B = [[1, 0, 0, 0, 1]] and C = [[0, 1, 0, 0]]. By using
Theorem 5, all eigenvalues are:
{−32,−
√
3
4
,−16, 16,
√
3
4
, 32}.
2. Main results and discussions
A general linear group GL(V ) of vector space V is the set of all
A ∈ End(V ), where A is invertible. A representation of a group G is
a homomorphism α : G → GL(V ) and the degree of α is equal to the
dimension of V . A trivial representation is a homomorphism α : G→ C∗,
where α(g) = 1, for all g ∈ G. Let ϕ : G→ GL(V ) be a representation with
ϕ(g) = ϕg, the character χϕ : G→ C of ϕ is defined as χϕ(g) = tr(ϕg). An
irreducible character is the character of an irreducible representation and
the character χ is linear, if χ(1) = 1. We denote the set of all irreducible
characters of G by Irr(G).
A character table is a matrix whose rows and columns are correspond
to the irreducible characters and the conjugacy classes of G, respectively.
Proposition 1 ([3]). Let G and H be two finite groups with character
tables M(G) and M(H), respectively. Then the character table of direct
product group G×H is
M(G×H) = M(G)⊗M(H).
The study of spectrum of Cayley graphs is closely related to irreducible
characters of G. If G is abelian, then the spectrum of X = Cay(G,S) can
easily be determined as follows.
Theorem 6 ([21]). Let S be a symmetric subset of abelian group G. Then
the eigenvalues of adjacency matrix of Cay(G,S) are given by
λϕ =
∑
s∈S
ϕ(s),
where ϕ ∈ Irr(G).
M. Ghorbani, M. Songhori 199
Let G be a finite group with symmetric subset S. We recall that S is a
normal subset if and only if Sg = g−1Sg = S, for all g ∈ G. The following
theorem is implicitly contained in [7, 21].
Theorem 7. Let G be a finite group with a normal symmetric subset S.
Let A be the adjacency matrix of the graph X = Cay(G,S). Then the
eigenvalues of A are given by [λϕ]
ϕ(1)2, where λϕ = 1
ϕ(1)
∑
s∈S ϕ(s) and
ϕ ∈ Irr(G).
Example 2. Consider the dihedral group D8 with the following presen-
tation
D8 = 〈a, b : a4 = b2 = 1, b−1ab = a−1〉.
The character table of dihedral group D8 is reported in Table 1. Let
S = {a, a−1}, then by using Theorem 7, all eigenvalues of D8 are:
λχ1
= λχ3
= 2, λχ2
= λχ4
= −2 and λχ5
= 0.
In other words, the spectrum of Cayley graph on group D8, where
S = {a, a−1} is as follows:
{[−2]2, [0], [2]2}.
M(D8) 1 g1 g2 g3 g4
χ1 1 1 1 1 1
χ2 1 −1 1 1 −1
χ3 1 1 −1 1 −1
χ4 1 −1 −1 1 1
ψ5 2 0 0 −2 0
Table 1. The character table of D8.
3. Spectra of Cayley graphs of order pqr
Given two groups G,H and a group homomorphism ϕ : H −→ Aut(G),
the semi-direct product of G and H with respect to ϕ denoted G⋊ϕ H
(or, simply, G ⋊ H) is a new group with set G × H and multiplication
operation (g1;h1)(g2;h2) = (g′1ϕ(h1)g2, h1h2). The aim of this section
is to compute the spectrum of Cayley graphs of order pqr by means of
semi-direct product. To do this, we first intoduce the presentation of these
group.
200 On the spectrum of Cayley graphs
A Frobenius group of order pq where p is prime and q|p− 1 is a group
of order pq by the following presentation:
Fp,q = 〈a, b : ap = bq = 1, b−1ab = au〉,
where u is an element of order q in multiplicative group Z∗
p. Let G be
a group of order pqr, where p > q > r are prime numbers. It is easy to
see that the Sylow p−subgroup P of G is normal. This means that G has
the following structure:
G ∼= Zp ⋊ϕ Zqr or Fq,r.
By using the concept of semi-direct product, Hölder in [17] classified
all groups of order pqr. Ghorbani and Nowroozi in [10] proved that a
group of order pqr is isomorphic with one of the following groups:
i) p = q = r, in this case there are five groups of order p3 as follows:
• P1 = Zp3 ,
• P2 = Zp × Zp2 ,
• P3 = Zp × Zp × Zp,
• P4 = Zp ⋊ Zp2 ,
• P5 = Zp ⋊ (Zp × Zp).
ii) p > q > r, then all groups of order pqr are
• G1 = Zpqr,
• G2 = Zr × Fp,q(q|p− 1),
• G3 = Zq × Fp,r(r|p− 1),
• G4 = Zp × Fq,r(r|q − 1),
• G5 = Fp,qr(qr|p− 1),
• Gi+5 = 〈a, b, c : ap = bq = cr = 1, ab = ba, c−1bc = bu, c−1ac =
av
i〉, where r|p − 1, q − 1, o(u) = r in Z∗
q and o(v) = r in
Z∗
p (1 6 i 6 r − 1).
iii) p < q and r = p, then all groups of order p2q are
• L1 = Zp2q,
• L2 = Zp × Zp × Zq,
• L3 = Zp × Fq,p (p|q − 1),
• L4 = Fq,p2 (p2|q − 1),
• L5 = 〈a, b : ap2 = bq = 1, a−1ba = bα, αp ≡ 1 (mod q)〉.
iv) q < p and r = p, then all groups of order p2q, where q | p− 1 are
• Q1 = Zp2q,
• Q2 = Zp × Zq × Zp,
• Q3 = Zp × Fp,q (q|p− 1),
• Q4 = Fp2,q (q|p2 − 1),
M. Ghorbani, M. Songhori 201
• Q5 = 〈a, b, c : ap = bq = cp = 1, ac = ca, b−1ab = aα, b−1cb =
cα
x
, αq ≡ 1 (mod p), x = 1, . . . , q − 1〉.
The general structures of groups Gi+5, Q5 and Q6 are in terms of
semi-direct product, namely Zr ⋉ (Zp × Zq). In [8] the spectra of Cayley
graphs Cay(Zm ⋊Zn, S) are studied. In continuing, by using some results
of representation theory, we propose the spectra of Cayley graphs of order
pqr, where p, q and r are prime numbers. A class of Zc ⋉ (Zm × Zn) has
a representation as follows:
Zc ⋉K (Zm × Zn)
= 〈x, y, z;xm = yn = zc = 1, ab = ba, zxz−1 = xk, zyz−1 = yk
′〉, (2)
where o(k) = c in Z∗
m, o(k′) = c in Z∗
n and K = (k, k′).
An embedding map is a homomorphism ψ : G −→ GLn(F), and we
say that the representation is faithful if ψ is injective. Here, we suppose
that the filed F is complex number C. Let G is a finite group and for
g ∈ G, Ag = A(Cay(G, {g})) is the adjacency matrix of related a Cayley
graph. If S ⊆ G, then AS = A(Cay(G,S)) and according to [8, Theorem
3.2], we have AS =
∑
s∈S As.
Theorem 8 ([8]). Given a group G and an element g ∈ G, consider the
set Γ = {Ag|g ∈ G} and the map ψ : G −→ Γ given by ψ(g) = Ag. Then,
ψ gives a faithful representation for G in GL|G|(Q).
The adjacency representation of group G is a representation given
by ψ. This is called the regular representation in the literature [24].
Definition 1. Let Ch be the h× h matrix with entries
cij =
{
1, j − i ≡ 1 (mod h)
0 otherwise.
This matrix is a circulant matrix or cyclic, since it is the adjacency
matrix of Cayley graph Zh with S = {x} where xh = id.
Definition 2. Suppose m, n and k satisfies in relation mk ≡ 1 (mod n).
Let Ωh be the m×m matrix with entries
Ωij =
{
ωhki−1
when (i = j),
0 otherwise,
202 On the spectrum of Cayley graphs
where ω = e
2πi
n is a primitive n-th root of unity. Clearly, for a ∈ Z,
(Ωh)
a = Ωha. On the other hand, the matrix (Ch)
l is given by
cij =
{
1, j − i ≡ l (mod h)
0 otherwise.
Now, let mk ≡ 1 (mod c) and nk
′ ≡ 1 (mod c)). Suppose X, Y and
Z are three mn×mn block matrices with the following blocks with c× c
order:
Xc×c =
Ω1 0
. . .
0 Ωmn
, Yc×c =
Ω′
1 0
. . .
0 Ω′
mn
,
and Zc×c =
Cc 0
. . .
0 Cc
.
It is simple to show Xn = I, Y m = I and Zc = I. If x, y and z are
generatores of Zm, Zn and Zc, respectivley then we have:
Theorem 9. Let G be a finite group and X, Y , Z be block matrices of
order mn × mn with blocks of order c × c. Three matrices X, Y and
Z are generators of a faithful representation of G = Zc ⋉K (Zm × Zn),
where K = (k, k′). Then G has a represention in (2), ϕ is injection and
ϕ(xaybzd) = XaY bZd.
Proof. See [8, Theorem 3.4].
The representation ϕ with conditions of Theorem 8 or 9 is called a
natural representation.
Theorem 10. The natural representation and adjacency represention of
Zc ⋉K (Zm × Zn), where K = (k, k′) are isomorphic.
Proof. We show tr(Axaybzd) = tr(XaY bZd). xaybzd = id iff XaY bZd = I
and so tr(Aid) = tr(I) = mnc. Let xaybzd 6= id. The adjacency repre-
sention of this element is Axaybzd . The Cayley graph Cay(Zc ⋉K (Zm ×
Zn), {xaybzd}) is simple and so there is no a non-zero element in the main
diagonal. This means that tr(Axaybzd) = 0. The natural representation of
xaybzd is XaY bZd, where
(XaY bZd)ij =
{
(Ωi)
a(Ω′
j)
b(Cc)
d, i = j,
0 otherwise.
M. Ghorbani, M. Songhori 203
If d ∤ c, all diagonal elements in the block matrix XaY bZd are zero and
then tr(Axaybzd) = 0. Let d | c, if a ∤ n and b ∤ m then the block ΩcaΩ
′
cb is
tr(ΩcaΩ
′
cb) = ωa · ω′b(1 + ωk · ω′k′ + · · ·+ ωkc−1 · ω′k′c−1
).
Then, for matrix XaY b we yield
tr(XaY b) = ωa · ω′bα+ ω2a · ω′2bα+ · · ·+ ωmna · ω′mnbα
= (ωa · ω′b + ω2a · ω′2b + · · ·+ ωmna · ω′mnb)α
= ωa · ω′b (ω
mna · ω′mnb − 1)
ωa · ω′b − 1
α,
where α = (1+ωk ·ω′k′ + · · ·+ωkc−1 ·ω′k′c−1
). So tr(XaY b) = 0 and these
two group representations are isomorphic.
Theorem 11. The characteristic polynomial of Cayley graph Cay(G,S),
where G is as represented in Eq. (2), is as follows:
χ(A(Zc ⋉K (Zm × Zn), S)) =
mn−1∏
i=0
χ
(
∑
xaybzd
ΩiaΩ
′
ib(Cc)
d
)
.
Proof. Let G = Zc ⋉K (Zm × Zn), where K = (k, k′) and
Zc ⋉ (Zm × Zn)
〈x, y, z;xm = yn = zc = 1, ab = ba, zxz−1 = xk, zyz−1 = yk
′〉,
where o(k) = c in Z∗
m and o(k′) = c in Z∗
n. It yields that
χ
(
A(Cay(G,S))
)
= χ
(
∑
s∈S
A
(
Cay(G, {s})
)
)
= χ
(
∑
s∈S
As
)
.
The element s ∈ G can be written uniquely as xaybzd, where 0 6 a < n,
0 6 y < m and 0 6 d < c. Then
χ
(
∑
xaybzd
Axaybzd
)
= χ
(
∑
xaybzd
XaY bZd
)
.
Therefore
mn−1∏
i=0
χ
(
∑
xaybzd∈S
(Ωi)
a(Ω′
i)
b(Cc)
d
)
=
mn−1∏
i=0
χ
(
∑
xaybzd∈S
(Ωia)(Ω
′
ib)(Ccd)
)
.
204 On the spectrum of Cayley graphs
By this formula, we can determine the characteristic polynomials of
Cayley graphs of groups Gi+5, L5, P5 and Q5.
Corollary 2. For the Frobenius group Fp,q, we have
χ(A(Zq ⋉k Zp, S)) =
q−1
∏
i=0
χ
(
∑
xayb
Ωia(Cq)
b
)
.
This result gives characteristic polynomials of Cay(G,S), where G ∈
{G5, L4, P4, Q4}. The spectrum of Cayley graphs of cyclic groups was
computed in [20] and this subject is a corollary of Theorem 11.
Proposition 2 ([20]). All eigenvalues of Cay(Zn;S) are given by
{
λ | λ =
∑
s∈S
ωxs, x ∈ Zn, 1 6 x 6 n
}
.
Hence, the characteristic polynomials of Cayley graphs of groups G1,
L1, P1 and Q1 are as follows:
Corollary 3. Let x be a generator of cyclic group Zn and y be a generator
of Zm. The eigenvalues of Cay(Zn × Zm, S), where S = {x, y} are
{λ|λ = ωi
n + ωj
m, 0 6 i < n, 0 6 j < m}.
By using Corollary 3, we can determine the spectra of Cayley graphs
of groups L2, P2, P3 and Q2.
Let Γ1 = Cay(Zc, S1) and Γ2 = Cay(Zn ⋊ Zm, S2) be two Cayley
graphs, then
Γ1 � Γ2
∼= Cay(Zc × (Zn ⋊ Zm), T ),
where T = {(s, 1)(1, t)|s ∈ S1, t ∈ S2}.
Corollary 4.
χ(Cay(Γ1 × Γ2, T )) = χ(Cay(Γ1, S1)).χ(Cay(Γ2, S2)).
By using Corollary 4 one can find the characteristic polynomial of
Cayley graph Cay(G,S), where G ∈ {G2, G3, G4, L3, Q3}.
Example 3. Let
P4 = 〈a, b : ap2 = bp = 1, b−1ab = ap+1〉 and S = {a, a1, b, b−1},
M. Ghorbani, M. Songhori 205
then the adjacency matrix of Cay(P4, S) is a p×p block matrix as following
form:
A = [Lp2 , Ip2 ,
p−3
︷ ︸︸ ︷
0, . . . , 0, Ip2 ] = Lp2 ⊗ Ip + Ip2 ⊗ [0, 1, 0, . . . , 0, 1],
where Lp2 = [0, 1, 0, . . . , 0, 1]. Then all eigenvalues of this matrix are
2 cos(2kπ
p2
) + 2 cos(2k
′π
p
), where 1 6 k 6 p2 and 1 6 k′ 6 p.
Example 4. Let
P5 = 〈a, b, c : ap = bp = cp = 1, [a, b] = c, [a, c] = [b, c] = 1〉
and
S = {a, a1, b, b−1},
then the adjacency matrix of Cay(P5, S) is a p2 × p2 block matrix, where
A = [Lp, I,
p−3
︷ ︸︸ ︷
0, . . . , 0, I,
p2−p
︷ ︸︸ ︷
0, . . . , 0] = Lp ⊗ Ip2 + Ip ⊗ [0, 1, 0, . . . , 0, 1]p2 ,
and L = [0, 1, 0, . . . , 0, 1]. So all eigenvalues of this matrix are λk + µk′ ,
where 1 6 k 6 p, 1 6 k′ 6 p2 and
λk = e
2πik
p + e
− 2πik
p , 1 6 k 6 p, µk′ = e
2πik′
p + e
− 2πik′
p , 1 6 k′ 6 p2.
References
[1] A. R. Abdollahi, A. Loghman, Cayley graphs isomorphic to the product of two
Cayley graphs, Ars Combin. Ars Combinatoria. 126 (2016) pp. 301–310.
[2] L. Babai, Spectra of Cayley Graphs, J. Combin. Theory Series B. 27 (1979)
pp. 180-189.
[3] R. A. Brualdi, D. Cvetković, A Combinatorial Approach to Matrix Theory and Its
Applications, Chapman and Hall/CRC; Second edition, (2008).
[4] G. Chapuy and V. Féray, A note on a Cayley graph of Sn 〈arXiv : 1202.4976v2〉.
[5] D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs-Theory and Application,
Deutscher Verlag der Wissenschaften, Berlin, Academic Press, third edition, Johann
Ambrosius Barth Verlag, (1995).
[6] M. DeVos, L. Goddyn, B. Mohar and R. Šámal, Cayley sum graphs and eigenvalues
of (3,6)-fullerenes, J. Comb. Theory Series. 99 (2009) pp. 358–369.
[7] P. Diaconis and M. Shahshahani, Generating a random permutation with random
transpositions, Zeit. für Wahrsch. verw. Gebiete 57 (1981) pp. 159–179.
[8] N. Fox, Spectra of Semidirect Products of Cyclic Groups, Rose-Hulman Undergrad-
uate Mathematics Journal 11(2) (2010) pp. 131–147.
206 On the spectrum of Cayley graphs
[9] M. Ghorbani, On the eigenvalues of normal edge-transitive Cayley graphs, Bulletin
of the Iranian Mathematical Society. 1 (2014) pp. 49–56.
[10] M. Ghorbani, F. Nowroozi Larki, Automorphism group of groups of order pqr,
Algebraic Structures and Their Applications. 41 (2015) pp. 101–107.
[11] M. Ghorbani, F. Nowroozi Larki, On the spectrum of Cayley graphs related to the
finite groups, Filomat. 31 (2017) pp. 6419–6429.
[12] M. Ghorbani, F. Nowroozi Larki, On the spectrum of Cayley graphs, Siberian
Electronic Mathematical Reports. 16 (2016) pp. 1283–1289.
[13] M. Ghorbani, F. Nowroozi Larki, On the spectrum of finite Cayley graphs, Jour-
nal of Discrete Mathematical Sciences and Cryptography, Journal of Discrete
Mathematical Sciences and Cryptography. 21 (2018) pp. 83–112.
[14] M. Ghorbani, A. Seyyed-Hadi, F. Nowroozi-Larki, Computing the eigenvalues of
graphs of order p2q, Journal of Algebraic Systems. 7 (2020) pp. 189–203.
[15] M. Ghorbani, M. Songhori, M. Rajabi-Parsa, Normal edge-transitive Cayley graphs
whose order are a product of three primes, Italian Journal of Pure and Applied
Mathematics. 39 (2018) pp. 628–635.
[16] C. D. Godsil, G. Royle, Algebraic Graph Theory, New York, Springer, (2001).
[17] H. Hölder, Die Gruppen der Ordnungen p3, pq2, pqr, p4, Math. Ann. (1893) pp. 371–
410.
[18] G. James, M. Liebeck, Representation and characters of groups, Cambridge Uni-
versity Press, Cambridge, (1993).
[19] R. Krakovski and B. Mohar, Spectrum of Cayley graphs on the symmetric group
generated by transpositions, Linear Algebra Appl. 437 (2012) pp. 1033–1039.
[20] J. Lazenby, Circulant Graphs and Their Spectra, Senior Thesis, Reed College,
Portland, OR, May (2008).
[21] S. L. Lee, Y. L. Luo, B. E. Sagan, Y.-N. Yeh, Eigenvectors and eigenvalues of
some special graphs, IV multilevel circulants. Int. J. Quant. Chem. 41 (1992)
pp.105-116.
[22] L. Lovász, Spectra of graphs with transitive groups, Period. Math. Hungar. 6 (1975)
pp. 191–196.
[23] B. E. Sagan, The Symmetric Group, second ed., Springer, New York, (2001).
[24] J. Serre, Linear Representations of Finite Groups, Springer, New York, (1977).
Contact information
Modjtaba Ghorbani,
Mahin Songhor
Department of Mathematics, Faculty of Science,
Shahid Rajaee Teacher Training University,
Tehran, 16785-136, I.R. Iran
E-Mail(s): mghorbani@sru.ac.ir,
mahinsonghori@gmail.com
Received by the editors: 03.10.2017.
mailto:mghorbani@sru.ac.ir
mailto:mahinsonghori@gmail.com
M. Ghorbani, M. Songhori
|