Paley-type graphs of order a product of two distinct primes
In this paper, we initiate the study of Paley-type graphs ГN modulo N = pq, where p, q are distinct primes of the form 4k + 1. It is shown that ГN is an edge-regular, symmetric, Eulerian and Hamiltonian graph. Also, the vertex connectivity, edge connectivity, diameter and girth of ГN are studied and...
Gespeichert in:
| Datum: | 2019 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2019
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/188476 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Paley-type graphs of order a product of two distinct primes / A. Das // Algebra and Discrete Mathematics. — 2019. — Vol. 28, № 1. — С. 44–59. — Бібліогр.: 17 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188476 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1884762023-03-03T01:27:08Z Paley-type graphs of order a product of two distinct primes Das, A. In this paper, we initiate the study of Paley-type graphs ГN modulo N = pq, where p, q are distinct primes of the form 4k + 1. It is shown that ГN is an edge-regular, symmetric, Eulerian and Hamiltonian graph. Also, the vertex connectivity, edge connectivity, diameter and girth of ГN are studied and their relationship with the forms of p and q are discussed. Moreover, we specify the forms of primes for which ГN is triangulated or trianglefree and provide some bounds (exact values in some particular cases) for the order of the automorphism group Aut(ГN) of the graph ГN, the chromatic number, the independence number, and the domination number of ГN. 2019 Article Paley-type graphs of order a product of two distinct primes / A. Das // Algebra and Discrete Mathematics. — 2019. — Vol. 28, № 1. — С. 44–59. — Бібліогр.: 17 назв. — англ. 1726-3255 2010 MSC: 05C30, 05C69 http://dspace.nbuv.gov.ua/handle/123456789/188476 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
In this paper, we initiate the study of Paley-type graphs ГN modulo N = pq, where p, q are distinct primes of the form 4k + 1. It is shown that ГN is an edge-regular, symmetric, Eulerian and Hamiltonian graph. Also, the vertex connectivity, edge connectivity, diameter and girth of ГN are studied and their relationship with the forms of p and q are discussed. Moreover, we specify the forms of primes for which ГN is triangulated or trianglefree and provide some bounds (exact values in some particular cases) for the order of the automorphism group Aut(ГN) of the graph ГN, the chromatic number, the independence number, and the domination number of ГN. |
| format |
Article |
| author |
Das, A. |
| spellingShingle |
Das, A. Paley-type graphs of order a product of two distinct primes Algebra and Discrete Mathematics |
| author_facet |
Das, A. |
| author_sort |
Das, A. |
| title |
Paley-type graphs of order a product of two distinct primes |
| title_short |
Paley-type graphs of order a product of two distinct primes |
| title_full |
Paley-type graphs of order a product of two distinct primes |
| title_fullStr |
Paley-type graphs of order a product of two distinct primes |
| title_full_unstemmed |
Paley-type graphs of order a product of two distinct primes |
| title_sort |
paley-type graphs of order a product of two distinct primes |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2019 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188476 |
| citation_txt |
Paley-type graphs of order a product of two distinct primes / A. Das // Algebra and Discrete Mathematics. — 2019. — Vol. 28, № 1. — С. 44–59. — Бібліогр.: 17 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT dasa paleytypegraphsoforderaproductoftwodistinctprimes |
| first_indexed |
2025-07-16T10:32:49Z |
| last_indexed |
2025-07-16T10:32:49Z |
| _version_ |
1837799291280687104 |
| fulltext |
“adm-n3” — 2019/10/20 — 9:35 — page 44 — #46
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 28 (2019). Number 1, pp. 44–59
c© Journal “Algebra and Discrete Mathematics”
Paley-type graphs of order a product of two
distinct primes∗
Angsuman Das
Communicated by D. Simson
Abstract. In this paper, we initiate the study of Paley-type
graphs ΓN modulo N = pq, where p, q are distinct primes of the
form 4k + 1. It is shown that ΓN is an edge-regular, symmetric,
Eulerian and Hamiltonian graph. Also, the vertex connectivity,
edge connectivity, diameter and girth of ΓN are studied and their
relationship with the forms of p and q are discussed. Moreover, we
specify the forms of primes for which ΓN is triangulated or triangle-
free and provide some bounds (exact values in some particular
cases) for the order of the automorphism group Aut(ΓN ) of the
graph ΓN , the chromatic number, the independence number, and
the domination number of ΓN .
1. Introduction
The Paley graph, named after Raymond Paley, forms an infinite family
of self-complementary, strongly regular graphs. Paley graph is a special
type of Cayley graph with a finite field Fq, q = pn where p is a Pythagorean
prime i.e., primes of the form 4k+1 as the additive group and the set of non-
zero quadratic residues in Fq as the connection set. Since its inception, due
to its connection with number theoretic properties of quadratic residues, a
lot of research has been done on Paley graphs [3],[4], [12] and its generalized
versions [1], [2], [7], [11], [16]. However, as far as our knowledge, Paley-type
∗Preliminary version of this work appears in proceedings of ICMC 2015 [5].
2010 MSC: 05C30, 05C69.
Key words and phrases: Cayley graph, quadratic residue, Pythagorean prime.
“adm-n3” — 2019/10/20 — 9:35 — page 45 — #47
A. Das 45
graphs on modulus of the form pq, where p and q are distinct primes
remained unexplored till date.
In this paper, we study Paley-type graphs ΓN modulo N = pq, where
p, q are distinct Pythagorean primes. The main goal of this paper is to
study the properties of the proposed Paley-type graphs and their deviation
from Paley graphs in terms of various graph parameters. It is shown that
ΓN is an edge-regular, Eulerian, Hamiltonian and arc-transitive graph.
Also, the vertex connectivity, edge connectivity, diameter and girth of ΓN
are studied. Moreover, the conditions under which ΓN is triangulated and
triangle-free are discussed. We also provide some bounds (exact value in
some particular cases) for the order of the automorphism group Aut(ΓN ) of
ΓN , the domination number, the chromatic number, and the independence
number of ΓN .
2. Preliminaries
In this section, for convenience of the reader and also for later use, we
recall some definitions and notations concerning integers modulo N and
quadratic residues in elementary number theory. For undefined terms and
concepts in graph theory the reader is referred to [8] and [15]. Throughout
this paper, graphs are undirected, simple and without loops.
An odd prime p is called a Pythagorean prime if p ≡ 1(mod 4).
Throughout this paper, even if it is not mentioned, a prime p always
means a Pythagorean prime and N = pq means the product of two
distinct Pythagorean primes. By ZN ,Z
∗
N ,QRN ,QNRN ,J +1
N ,J −1
N , we
mean the set of all integers modulo N , the set of all units in integers
modulo N , the set of all quadratic residues and non-quadratic residues
which are also units in integers modulo N , the set of all units in integers
modulo N with Jacobi symbol +1 and −1 respectively. For the sake of
convenience, a ≡ b(mod N) is sometimes written as a = b, in places where
the modulus is clear from the context. We can conclude the following
lemma from the results which can be found in any elementary number
theory book e.g., [14].
Lemma 1. If N = pq, then the following are true:
• J +1
N is a subgroup of Z∗
N and QRN is a subgroup of J +1
N .
• |Z∗
N | = φ(N) = (p − 1)(q − 1), |J +1
N | = |J −1
N | = (p−1)(q−1)
2 and
|QRN | = (p− 1)(q − 1)
4
, where φ denotes the Euler’s Phi function.
• x ∈ QRN ⇐⇒ x ∈ QRp ∩ QRq.
“adm-n3” — 2019/10/20 — 9:35 — page 46 — #48
46 Paley-type Graphs of Order pq
• x ∈ J +1
N \ QRN ⇐⇒ x ∈ QNRp ∩ QNRq.
• x ∈ J −1
N ⇐⇒ x ∈ QNRp ∩ QRq or x ∈ QRp ∩ QNRq.
Lemma 2. If p, q are two distinct primes of the form p ≡ q ≡ 1(mod 4),
then −1 is a quadratic residue in ZN .
Proof. To show that −1 is a quadratic residue in ZN , we need to show
that x2 ≡ −1(mod N) has a solution. But,
x2 ≡ −1(mod N) ⇔ x2 ≡ −1(mod p) and x2 ≡ −1(mod q)
Now, as p and q are Pythagorean primes, −1 is a square in both Zp and
Zq. Thus, x2 ≡ −1(mod N) have a solution in ZN .
3. Paley-type graph modulo N
We now define the Paley-type graphs ΓN modulo N = pq and study
some of their basic properties.
Definition 1 (Paley-type Graph modulo N). For N = pq, Paley-type
Graph modulo N , ΓN is given by ΓN = (V,E), where V = ZN and
(a, b) ∈ E ⇔ a− b ∈ QRN .
Remark 1. ΓN is a Cayley Graph (G,S) where G = (ZN ,+) and S =
QRN . Observe that as −1 ∈ QRN and QRN is a group with respect
to modular multiplication, QRN is also closed with respect to additive
inverse, i.e., S = −S and 0 6∈ S.
Theorem 1. ΓN is Hamiltonian and hence connected.
Proof. Since, 1 ∈ QRN , the vertex set {0, 1, 2, . . . , N − 1}, taken in order,
can be thought of as a Hamiltonian path. Hence, the theorem is proved.
Theorem 2. ΓN is regular with valency φ(N)/4 and hence Eulerian.
Proof. Let x ∈ ZN . By N(x), we mean the set of vertices in ΓN which
are adjacent to x, i.e., N(x) = {z ∈ ZN : x− z ∈ QRN}. If possible, let
∃z1, z2 ∈ N(x) with z1 6= z2 such that x − z1 = x − z2. But, x − z1 =
x − z2 = s (say) ∈ QRN ⇒ z1 = x − s = z2, a contradiction. Thus,
∀s ∈ QRN , ∃ a unique z ∈ ZN such that x − z = s. Thus, degree or
valency of x = |N(x)| = |QRN | = φ(N)/4. Now, let p = 4k+1, q = 4l+1.
Since, degree of each vertex = φ(N)
4 = (p−1)(q−1)
4 = 4k·4l
4 = 4kl is even, ΓN
is Eulerian.
“adm-n3” — 2019/10/20 — 9:35 — page 47 — #49
A. Das 47
Note. The graph ΓN is not strongly regular (See Remark 3).
Remark 2. ΓN is not self-complementary: A necessary condition for a
self - complementary graph G with n vertices is that number of edges
in G equals n(n−1)
4 . But, the number of edges in ΓN with N vertices
is N ·φ(N)
8 < N(N−1)
4 . However, the next theorem shows that ΓN has a
homomorphic image of itself as a sub-graph of its complement graph.
Theorem 3. ΓN has a homomorphic image of itself as a sub-graph of its
complement graph Γc
N .
Proof. Let n ∈ Z∗
N \ QRN . We define a function ψ : ΓN → Γc
N given by
ψ(x) = nx. For injectivity, ψ(x1) = ψ(x2) ⇒ nx1 = nx2 ⇒ x1 = x2, as
n is a unit in ZN . For homomorphism, x, y adjacent in ΓN ⇒ x − y ∈
QRN ⇒ n(x− y) 6∈ QRN ⇒ nx and ny are not adjacent in ΓN , i.e, ψ(x)
and ψ(y) are adjacent in Γc
N .
Theorem 4. ΓN is isomorphic to the direct product of Γp and Γq, the
Paley graphs of prime order p and q respectively, i.e., ΓN
∼= Γp × Γq.
Proof. Consider the map Φ : ΓN → Γp × Γq given by Φ(x) = (x mod p,
x mod p). Clearly, this is a bijection. The fact that Φ preserves adjacency
and non-adjacency follows from the result that QRN is isomorphic to
QRp ×QRq.
4. Symmetricity of ΓN
In this section, we study the action of the automorphism group Aut(ΓN )
on ΓN and its consequences.
Theorem 5. ΓN is vertex-transitive.
Proof. As ΓN is a Cayley graph, it is vertex transitive. (by Theorem 3.1.2
in [8]) However, we show the existence of such automorphisms explicitly,
which will be helpful later.
Choose a ∈ QRN and b ∈ ZN and define a function ϕ : ZN → ZN
given by ϕ(x) = ax+b, ∀x ∈ ZN . We show that ϕ is an automorphism. ϕ is
injective, for ϕ(x1) = ϕ(x2) ⇒ ax1+b = ax2+b⇒ a(x1−x2) = 0 ⇒ x1 =
x2 as a ∈ Z∗
N For surjectivity, ∀y ∈ ZN , ∃x = a−1y−a−1b ∈ ZN such that
ϕ(x) = a(a−1y − a−1b) + b = y. Moreover, ϕ is a graph homomorphism,
as x and y are adjacent in ΓN ⇔ x − y ∈ QRN ⇔ a(x − y) + b − b ∈
QRN ⇔ (ax+ b)− (ay + b) ∈ QRN ⇔ ϕ(x)− ϕ(y) ∈ QRN ⇔ ϕ(x) and
ϕ(y) are adjacent in ΓN . Thus, ϕ ∈ Aut(ΓN ).
“adm-n3” — 2019/10/20 — 9:35 — page 48 — #50
48 Paley-type Graphs of Order pq
Now, let u, v ∈ ZN be two vertices of ΓN . We take a = 1 ∈ QRN and
b = v−u ∈ ZN . Then the map ϕ : ZN → ZN given by ϕ(x) = ax+ b is an
automorphism on ΓN such that ϕ(u) = v. Thus, Aut(ΓN ) acts transitively
on ZN i.e., V (ΓN ).
Theorem 6. ΓN is arc-transitive and hence edge transitive.
Proof. Let {u1, v1}, {u2, v2} be two edges (considered as having a direc-
tion) in ΓN . Therefore, u1−v1, u2−v2 ∈ QRN . We take a = (u2−v2)(u1−
v1)
−1 ∈ QRN and b = u2 − au1 ∈ ZN and construct the automorphism
ϕ(x) = ax+ b as in Theorem 5. Since ϕ(u1) = u2 and ϕ(v1) = v2, ΓN is
arc transitive, and hence edge transitive.
Corollary 1. |Aut(ΓN )| > Nφ(N)
4 .
Proof. In Theorem 5, it was shown that ϕ : ZN → ZN given by ϕ(x) =
ax+ b, ∀x ∈ ZN is an automorphism for a ∈R QRN and b ∈R ZN . Thus,
|Aut(ΓN )| > Nφ(N)
4 .
Corollary 2. Edge connectivity of ΓN is φ(N)/4.
Proof. Since ΓN is connected and vertex-transitive, by Lemma 3.3.3 in
[8], its edge connectivity is equal to its valency.
Lemma 3. [8] The vertex connectivity of a connected edge transitive graph
is equal to its minimum valency.
Corollary 3. Vertex connectivity of ΓN is φ(N)/4.
Proof. Since, ΓN is a connected edge-transitive graph with valency φ(N)
4 ,
by Lemma 3, ΓN has vertex connectivity φ(N)/4.
5. Diameter, girth and triangles of ΓN
In this section, we find out the diameter and girth of ΓN . It is noted
that ΓN has dual nature when it comes to diameter and girth. To be more
specific, it depends on whether 5 is a factor of N or not. If 5 is one of the
two factors of N , we call it ΓN of Type-I and else call it ΓN of Type-II.
First, we prove two lemmas which will be used later.
Lemma 4. Let p be a prime of the form 4k + 1 and c ∈ Zp. Then, the
number of ways in which c can be expressed as difference of two quadratic
residues in Z∗
p are
“adm-n3” — 2019/10/20 — 9:35 — page 49 — #51
A. Das 49
(1) p−1
2 if c ≡ 0(mod p);
(2) p−5
4 if c ∈ QRp;
(3) p−1
4 if c ∈ QNRp.
Proof. (1) If c ≡ 0(mod p), then for all r ∈ QRp, c can be expressed as
r − r. Thus, the number in this case, is equal to number of elements in
QRp, i.e., p−1
2 .
(2) For this case, assume that c 6≡ 0(mod p), i.e., c ∈ Z∗
p. Let c =
a2 − b2 = (a + b)(a − b), where a, b ∈ Z∗
p. Now, for all p − 1 values of
d ∈ Z∗
p, letting a+ b = d; a − b = c
d
, we get all possible solutions of the
equation c = a2 − b2. From this, we get a = 1
2
(
d+ c
d
)
and b = 1
2
(
d− c
d
)
.
However, we need to ensure that a, b ∈ Z∗
p, i.e., d ± c
d
6≡ 0(mod p), i.e,
d2 6≡ ±c(mod p).
Now, if c ∈ QRp, then −c ∈ QRp. (as −1 is a quadratic residue in
Z∗
p). In this case, there exist two square roots of c and two other square
roots of −c. Thus, we loose 4 possible values of d. Thus, the number of
solutions is reduced to p− 5. Moreover, it is observed that the 4 solutions
of (a+ b, a− b), namely (d, c
d
), (−d, c
−d
), ( c
d
, d), ( c
−d
,−d) lead to the same
solution
a2 =
1
4
(
d+
c
d
)2
; b2 =
1
4
(
d− c
d
)2
(As p is odd, d 6= −d). Thus, the number of distinct solutions is reduced
to p−5
4 .
(3) The proof for c ∈ QNRp follows exactly using same arguments
except the fact that in this case, we do not loose those four solutions as
c 6≡ ±d2. Thus, the number of ways c can be expressed as difference of
quadratic residues is p−1
4 .
Lemma 5. Let N = pq, where p, q are Pythagorean primes. Then
1) If c ∈ QRN , then the number of ways in which c can be expressed
as difference of two quadratic residues, i.e., c = x2 − y2, x, y ∈ Z∗
N
is (p−5)(q−5)
16 .
2) If c ∈ J +1
N \ QRN , then the number of ways in which c can be
expressed as difference of two quadratic residues is (p−1)(q−1)
16 .
3) If c ∈ J −1
N , then the number of ways in which c can be expressed as
difference of two quadratic residues is either (p−1)(q−5)
16 [if c ∈ QRq,
but c 6∈ QRp] or (p−5)(q−1)
16 [if c ∈ QRp, but c 6∈ QRq].
4) If c( 6= 0) ∈ ZN \ Z∗
N i.e., c is a non-zero, non-unit in ZN , then
“adm-n3” — 2019/10/20 — 9:35 — page 50 — #52
50 Paley-type Graphs of Order pq
(a) If c ≡ 0(mod q) and c ∈ QRp, then the number of ways in
which c can be expressed as difference of two quadratic residues
is (p−5)(q−1)
8 .
(b) If c ≡ 0(mod q) and c ∈ QNRp, then the number of ways in
which c can be expressed as difference of two quadratic residues
is (p−1)(q−1)
8 .
(c) If c ≡ 0(mod p) and c ∈ QRq, then the number of ways in
which c can be expressed as difference of two quadratic residues
is (q−5)(p−1)
8 .
(d) If c ≡ 0(mod p) and c ∈ QNRq, then the number of ways in
which c can be expressed as difference of two quadratic residues
is (q−1)(p−1)
8 .
Proof. 1) If c ∈ QRN , then c ∈ QRp and c ∈ QRq. Thus, the result
follows from Chinese Remainder Theorem and second part of Lemma 4.
2) If c ∈ J +1
N \ QRN , then c ∈ QNRp and c ∈ QNRq. Thus, the
result from Chinese Remainder Theorem and third part of Lemma 4.
3) If c ∈ J −1
N , then either of two cases may arise, namely c ∈ QRq; c ∈
QNRp or c ∈ QRp; c ∈ QNRq.
If c ∈ QRq; c ∈ QNRp, then by applying second part of Lemma 4 for
q and third part of Lemma 4 and Chinese Remainder Theorem, we get
the count as (p−1)(q−5)
16 . Similarly, the case c ∈ QRp; c ∈ QNRq follows.
4) As c ∈ ZN \ Z∗
N , either p | c or q | c [not both, as that would imply
c ≡ 0(mod N)].
If q | c and p ∤ c, two cases arises, namely (a) c ≡ 0(mod q) and
c ∈ QRp, and (b) c ≡ 0(mod q) and c ∈ QNRp. In both the cases, the
lemma follows from Chinese remainder Theorem and Lemma 4.
Similarly, if q ∤ c and p | c, two cases arises, namely (c) c ≡ 0(mod p)
and c ∈ QRq and (d) c ≡ 0(mod p) and c ∈ QNRq. Again, these cases
follows similarly.
5.1. ΓN of Type-I
Lemma 6. If N = 5q, then x, y ∈ QRN ⇒ x− y 6∈ QRN .
Proof. Since x, y ∈ QRN , ∃a, b ∈ Z∗
N such that x ≡ a2(mod N) and
y ≡ b2(mod N). If possible, let x − y ∈ QRN . Then, ∃c ∈ Z∗
N such
that x − y ≡ c2(mod N). Therefore, a2 − b2 ≡ c2(mod N) ⇒ a2 ≡
b2 + c2(mod N) ⇒ a2 ≡ b2 + c2(mod 5). Now, as a, b, c ∈ Z∗
N , a, b, c are
relatively prime to 5. But a2 ≡ b2 + c2(mod 5) has no solution in Z∗
5,
which is a contradiction.
“adm-n3” — 2019/10/20 — 9:35 — page 51 — #53
A. Das 51
Theorem 7. If N = 5q, then ΓN is triangle-free.
Proof. If possible, let x, y, z ∈ ZN be vertices of a triangle in ΓN . Then,
x− y, z − y, x− z ∈ QRN . However, x− z ≡ (x− y)− (z − y)(mod N),
a contradiction to Lemma 6. Thus, ΓN is triangle-free.
Corollary 4. ΓN of Type-I is an edge-regular graph with parameters
v = 5q, k = q − 1, λ = 0.
Lemma 7. [8] If G is an abelian group and S is an inverse-closed subset
of G \ {e} with |S| > 3, then the Cayley graph (G,S) has girth at most
4.
Corollary 5. If N = 5q, then girth(ΓN ) = 4.
Proof. Since, ΓN is triangle-free, girth(ΓN ) > 4. However, as ΓN is a
Cayley graph with G = ZN and generating set S = QRN such that |S| =
q− 1 > 3, by Lemma 7, girth(ΓN ) is at most 4. Thus, girth(ΓN ) = 4.
Now, with the help of the following two lemmas, we prove that if
N = 5q, where q is a Pythagorean prime, then diam(ΓN ) = 3.
Lemma 8. If N = 5q, where q is a Pythagorean prime, then the number
of vertices at distance 2 from the vertex 0 ∈ ΓN is 3q − 1.
Proof. Let x be a vertex at distance 2 from 0. Clearly, x 6= 0. Since,
d(0, x) 6= 1, it follows that x 6∈ QRN . Also, as d(0, x) = 2, ∃u ∈ ΓN such
that 0, u are adjacent and u, x are adjacent i.e., u, u − x ∈ QRN , i.e.,
x = u− (u− x) can be expressed as difference of two quadratic residues
modulo N . Thus, number of vertices x at distance 2 from the vertex 0 is
equal to the number of x 6∈ QRN which can be expressed as difference of
two quadratic residues. Now, we finish the proof by appeal to Cases 2,3
and 4 of Lemma 5 with p = 5.
Case 2: The number of such x ∈ J +1
N \ QRN , i.e., |J +1
N \ QRN | is
(p−1)(q−1)
4 = q − 1.
Case 3: In J −1
N , only those x’s, for which x ∈ QRq but x 6∈ QR5, can
be expressed as difference of two quadratic residues. Note that the other
type of x’s can not be expressed as difference of quadratic residues as p = 5.
Thus, the number of x ∈ J −1
N which can be expressed as difference of two
quadratic residues is |{x ∈ J −1
N : x ∈ QRq & x 6∈ QR5}| =
(
q−1
2
)
2 =
q − 1.
Case 4: If x is a non-zero, non-unit element in ZN , out of the four
cases in Lemma 5, the last three cases are applicable. Note that in the
“adm-n3” — 2019/10/20 — 9:35 — page 52 — #54
52 Paley-type Graphs of Order pq
first case x can not be expressed as difference of quadratic residues as
p = 5. Thus, the number of x which can be expressed as difference of two
squares in this category is
|{x : x ≡ 0(mod q) & x ∈ QNR5}| + |{x : x ≡ 0(mod 5) & x ∈ QRq}|
+ |{x : x ≡ 0(mod 5) & x ∈ QNRq}|
=
5− 1
2
+
q − 1
2
+
q − 1
2
= q + 1
Combining all these cases, we get the total number of vertices at a distance
2 from the vertex 0 as (q − 1) + (q − 1) + (q + 1) = 3q − 1.
Lemma 9. If N = 5q, where q is a Pythagorean prime, then the number
of vertices at distance 3 from the vertex 0 ∈ ΓN is q + 1.
Proof. From the proof of Lemma 8, it is evident that x’s which are not at
a distance 1 or 2 from the vertex 0 fall under either of the two categories:
(i) x ∈ J −1
N , with x ∈ QR5, but x 6∈ QRq or (ii) x is a non-zero, non-unit
in ZN such that x ≡ 0(mod q) and x ∈ QR5. Observe that in both the
cases, x ∈ QR5.
We now construct a path of length 3 from 0 to x. Consider the vertex
1 and x. Now, x− 1 6∈ QR5, otherwise, we get two consecutive integers
x, x− 1 ∈ QR5, which is a contradiction. Thus, by Lemma 5, d(x, 1) =
d(x− 1, 0) = 2 or 1. Also, d(1, x) 6= 1 as that would give a path 0, 1, x of
length 2 from 0 to x, a contradiction. Hence, d(1, x) = 2. Let the shortest
path from 1 to x be 1, u, x. Then, 0, 1, u, x is a path from 0 to x and hence,
d(0, x) 6 3. On the other hand, d(0, x) 6= 1, 2. Thus, d(0, x) = 3.
Now, the number of such x’s at a distance 3 from 0 is
|{x ∈ J −1
N : x ∈ QR5;x 6∈ QRq}|
+ |{x ∈ ZN : x ≡ 0(mod q);x ∈ QR5}|
= 2
(
q − 1
2
)
+
5− 1
2
= (q − 1) + 2 = q + 1.
Theorem 8. If N = 5q, with q a Pythagorean prime, then diam(ΓN ) = 3.
Proof. Since, ΓN is regular with degree φ(N)/4 = q−1, number of vertices
adjacent to 0, i.e., at distance 1 from 0 is q − 1. By Lemma 8, Lemma 9
and counting the point 0 itself, we get the number of all points at distance
0, 1, 2, 3 from the vertex 0 as 1 + (q − 1) + (3q − 1) + (q + 1) = 5q = N .
Thus, it exhausts all the vertices in ΓN , i.e., all the points, apart from 0
itself, are at either distance 1, 2 or 3 from 0. Since, ΓN is symmetric, the
maximum distance between any two vertex is 3, i.e., diam(ΓN ) = 3.
“adm-n3” — 2019/10/20 — 9:35 — page 53 — #55
A. Das 53
5.2. ΓN of Type-II
Theorem 9. If N = pq where 5 ∤ N , then ΓN is triangulated and
girth(ΓN ) = 3.
Proof. Let x ∈ ZN be any vertex in ΓN . Consider x, x+ 32, x+ 52 ∈ ZN .
These three vertices form a triangle as 9, 16, 25 are relatively prime to N
and belongs to QRN . Thus, every vertex x ∈ ΓN is a vertex of a triangle
in ΓN . Hence, ΓN is triangulated. Now, existence of triangle in ΓN ensures
its girth to be 3.
Lemma 10. Let N = pq where 5 ∤ N . If 0, x ∈ ZN be non-adjacent
vertices in ΓN , then ∃u ∈ ZN such that 0 and u are adjacent and u and x
are adjacent.
Proof. Since, 0, x ∈ ZN be non-adjacent vertices in ΓN , x is not a quadratic
residue in ZN . Also, N = pq with 5 ∤ N implies p, q > 5. Therefore, by
Lemma 5, x can always be expressed as difference of two quadratic residues,
say u, v ∈ QRN such that x = u−v. Since, u ∈ QRN , 0 and u are adjacent
in ΓN . Also, u− x = v is a quadratic residue, i.e., u and x are adjacent
in ΓN .
Theorem 10. If N = pq where 5 ∤ N , then diam(ΓN ) = 2.
Proof. Let x, y ∈ ZN . If x − y ∈ QRN , then d(x, y) = 1. If x − y is not
a quadratic residue, then 0 and x − y are non-adjacent vertices in ΓN .
Therefore, by Lemma 10, ∃u ∈ ZN such that 0 is adjacent to u and u
is adjacent to x − y. So using a translation of y, we get y is adjacent
to u+ y and u+ y is adjacent to x in ΓN . Thus, d(x, y) = 2 and hence
diam(ΓN ) = 2.
Theorem 11. Let N = pq, where p, q > 5 are primes with p = 4k+1, q =
4l + 1. If x, y are two adjacent vertices in ΓN , then there are exactly
(k − 1)(l − 1) vertices in ΓN which are adjacent to both x and y.
Proof. Since x, y are two adjacent vertices in ΓN , x−y ∈ QRN . By Lemma
5, the number of ways in which x − y can be expressed as difference of
two quadratic residues is (p−5)(q−5)
16 = (4k−4)(4l−4)
16 = (k − 1)(l − 1). Let
x−y = u−v where u, v ∈ QRN . Therefore, 0, u are adjacent (as u ∈ QRN )
and u, x− y are adjacent (as u− (x− y) = v ∈ QRN ) in ΓN . Thus, by
using a translation by y and symmetricity of ΓN , y, u+ y are adjacent
and u+ y, x are adjacent. Hence, there are exactly (k − 1)(l − 1) vertices
in ΓN which are adjacent to both x and y.
“adm-n3” — 2019/10/20 — 9:35 — page 54 — #56
54 Paley-type Graphs of Order pq
Corollary 6. ΓN of Type-II is edge-regular with parameters v = pq, k =
(p−1)(q−1)
4 , λ = (p−5)(q−5)
16 .
Remark 3. By Theorem 2 and Theorem 11, it follows that ΓN of Type-II
is regular and any two neighbours in ΓN have equal number of common
neighbours. However, any two non-adjacent vertices may not have equal
number of common neighbours. Thus, ΓN is not strongly regular.
In Theorem 9, it was shown that ΓN of Type-II is triangulated. Now,
by using Theorem 11, we count the number of triangles in ΓN of Type-II.
Theorem 12. If N = pq with p = 4k + 1, q = 4l + 1 being primes > 5,
then number of triangles in ΓN is 2
3Nk(k − 1)l(l − 1).
Proof. Let x be a vertex in ΓN . The number of vertices adjacent to x is
φ(N)/4. Let y be one of those vertices adjacent to x. Now, by Theorem
11, there are (k − 1)(l − 1) vertices zi’s in ΓN which are adjacent to both
x and y, thereby forming a triangle. Thus, the count of triangles with x as
a vertex, comes to φ(N)
4 (k − 1)(l − 1). However, this number is twice the
actual number of triangles with x as a vertex, since we could have also
started with choosing zi instead of y and get y as the common neighbour
of x and zi. Thus, the actual number of triangles with x as a vertex is
φ(N)
8 (k − 1)(l − 1). Now, varying x over the vertex set of ΓN , the count
becomes φ(N)
8 N(k − 1)(l − 1). Again, this count is to be divided by 3, as
if x, y, z are vertex of a triangle, then the triangle is counted thrice once
with respect to each vertex. Thus, the actual number of triangles in ΓN is
φ(N)
24
N(k − 1)(l − 1) =
(p− 1)(q − 1)
24
N(k − 1)(l − 1)
=
4k · 4l
24
N(k − 1)(l − 1) =
2
3
Nk(k − 1)l(l − 1).
Remark 4. Note that one of k − 1, k, k + 1 is divisible by 3. But as
p = 4k + 1 = 3k + (k + 1), k + 1 is not divisible by 3, thus k(k − 1) is
divisible by 3. As a result, the number of triangles is a positive integer.
6. Independence number of ΓN
In this section, we find the independence number of ΓN of Type-I and
provide both lower and upper bounds for that of ΓN of Type-II. We first
state a result which will be crucial in deducing these bounds.
“adm-n3” — 2019/10/20 — 9:35 — page 55 — #57
A. Das 55
Proposition 1. [17] If G and H are vertex-transitive graphs, then inde-
pendence number of their direct product G×H is given by α(G×H) =
max{α(G) · |H|, α(H) · |G|}.
Theorem 13. If N = pq with p < q, then 2q 6 α(ΓN ) 6 q[
√
p].
Proof. Since, Paley graphs are self complementary, clique number of Γp=
independence number of Γp, i.e., ω(Γp) = α(Γp). Also, it is known that
clique number of a prime-order Paley graph ω(Γp) <
√
p (See [4]). Now,
as p < q and p, q are primes of the form 1 mod 4, ∃k ∈ N such that
q = 4k + p. Thus,
p2q = p2(p+ 4k) = p3 + 4p2k < p3 + 8p2k + 16pk2 = p(p+ 4k)2 = pq2
i.e., p
√
q < q
√
p. Since ΓN
∼= Γp × Γq and Paley graphs are vertex-
transitive, by Proposition 1 we get α(ΓN ) = max{q · α(Γp), p · α(Γq)} <
max{p√q, q√p} = q
√
p. In fact, as ω(Γp) is a positive integer, α(ΓN ) 6
q[
√
p].
For the lower bound, choose a ∈ QNRp and consider the following
subset of ZN ,
I = {pk : 0 6 k 6 q − 1} ∪ {pl + a : 0 6 l 6 q − 1}
Claim: I is an independent subset of ΓN of size 2q.
Proof of the claim: As the difference of two elements of the form pk is a
multiple of p, the difference does not belong to QRp and as a result does
not belong to QRN . Thus, two vertices of the form pk are non-adjacent
in ΓN . Similarly, two vertices of the form pl + a are non-adjacent in ΓN .
Finally, as (pl+ a)− pk ≡ a mod p, (pl+ a)− pk does not belong to QRp
and hence does not belong to QRN . Thus, a vertex of the form pk is not
adjacent to a vertex of the form pl + a. Therefore the claim is true and it
proves the required lower bound of α(ΓN ).
In the next corollary, we show that the lower bound is tight.
Corollary 7. For ΓN of Type-I, α(ΓN ) = 2q.
Proof. As Γ5 is a cycle of length 5, α(Γ5) = 2. Also for Paley graph Γq,
α(Γq) <
√
q. Thus,
α(ΓN ) = max{q · α(Γ5), 5 · α(Γq)} 6 max{2q, 5√q} = 2q.
The last equality follows as 2q > 5
√
q for all q > 25
4 and the least value
of q in ΓN of Type-I is 13. Hence, α(ΓN ) 6 2q. Now, as demonstrated in
Theorem 13, I is an independent set of size 2q. Thus, α(ΓN ) = 2q.
“adm-n3” — 2019/10/20 — 9:35 — page 56 — #58
56 Paley-type Graphs of Order pq
In fact, a maximal independent set in ΓN is a collection of vertices of
the form {x ∈ ZN : x = 5k or x = 5l + 3 for 0 6 k, l 6 q − 1}. It is easy
to check that this set contains 2q elements and independence of the set
follows from the fact that 0 and 3 does not belong to QR5.
7. Chromatic number of ΓN
In this section, we find the chromatic number of ΓN of Type-I and
provide both lower and upper bounds for that of ΓN of Type-II. Before
that, we state two results which will be used in deducing these bounds.
Proposition 2. (See [9]; p.22) For any graph G with vertex set V , χ(G) ·
α(G) > |V |.
Proposition 3. For graphs G and H, χ(G×H) 6 min{χ(G), χ(H)}.
Proof. The proof follows from the existence of projection graph homomor-
phisms G×H → G and G×H → H.
Lemma 11. For ΓN of Type-I, χ(ΓN ) > 3.
Proof. Since,N = 5q and q is a prime of the form 4k+1, the minimum value
of q is 13 and hence, the minimum value of N is 65. We now demonstrate
a 5-cycle in ΓN , as existence of such cycle will ensure χ(ΓN ) > χ(C5) = 3.
Consider the vertices 0, 1, 17, 8, 4 in ΓN . They form a 5-cycle in ΓN ,
taken in order, as 1, 4, 9, 16 ∈ QRN , thereby proving the lemma.
Theorem 14. For ΓN of Type-I, χ(ΓN ) = 3.
Proof. Since Paley graph of q vertices Γq for q > 5 is triangulated, χ(Γq) >
3. Moreover, Γ5
∼= C5 and χ(C5) = 3. Therefore, from Theorem 3 it follows
that χ(ΓN ) 6 min{χ(Γ5), χ(Γq)} = min{χ(C5), χ(Γq)} 6 3. Combining
this with Lemma 11, the theorem follows.
Remark 5. It is also possible to find an explicit 3-coloring for ΓN of
Type-I. Consider the sets X1 = {x ∈ ZN : x ≡ 0 mod 5 or x ≡ 2 mod 5},
X2 = {x ∈ ZN : x ≡ 1 mod 5 or x ≡ 3 mod 5} and X3 = {x ∈ ZN : x ≡
4 mod 5}. We will show that X1, X2 and X3 are independent sets whose
union is ZN . As a result, they form color classes of ΓN .
Let a, b ∈ X1. If both are congruent to 0 mod 5 or 2 mod 5, then
their difference is also 0 mod 5 and as a result does not belong to QR5
and hence does not belong to QRN . If a ≡ 0 mod 5 and b ≡ 2 mod 5,
then a− b ≡ 2 mod 5. Thus a− b 6∈ QR5 and hence does not belong to
“adm-n3” — 2019/10/20 — 9:35 — page 57 — #59
A. Das 57
QRN . Thus, X1 is an independent set. The proof for X2 and X3 follows
similarly.
Theorem 15. For ΓN of Type-II, if p < q, then
√
p < χ(ΓN ) 6 min{χ(Γp), χ(Γq)}.
Proof. From Theorem 13, α(ΓN ) < q
√
p. Now, by Proposition 2, we have
χ(ΓN ) >
|ZN |
α(ΓN )
>
pq
q
√
p
=
√
p.
Other part of the inequality follows from Proposition 3.
8. Domination number of ΓN
In this section, we provide some bounds for domination number of ΓN .
Before that, we state two results which will be used in deducing these
bounds.
Proposition 4. [10] Let G be a graph with n vertices.
1) If G has a degree sequence d1, d2, . . . , dn with di > di+1, then
γ(G) > min{k : k + (d1 + d2 + . . .+ dk) > n}.
2) If G has no isolated vertex and has minimum degree δ(G), then
γ(G) 6
n
δ(G) + 1
δ(G)+1
∑
j=1
1
j
.
Theorem 16. If N = pq, then γ(ΓN ) > 5. In particular, if N = 5q, then
5 6 γ(ΓN ) 6 5
q
∑
j=1
1
j
.
Proof. For the first part, we assume that p = 4l + 1. Since, ΓN is regular
with degree φ(N)
4 = (p−1)(q−1)
4 = l(q − 1), we have γ(ΓN ) > min{k :
k + kl(q − 1) > (4l + 1)q} = 5.
For the second part, i.e., N = 5q, we put l = 1. Also, as ΓN has no
isolated vertex,
γ(ΓN ) 6
5q
(q − 1) + 1
q
∑
j=1
1
j
= 5
q
∑
j=1
1
j
.
Remark 6. A similar upper bound could have been given for the general
case, however the expression being messy, may not provide meaningful
insight.
“adm-n3” — 2019/10/20 — 9:35 — page 58 — #60
58 Paley-type Graphs of Order pq
9. Conclusion and future work
In this paper, we introduced Paley-type graphs on composite modulus
and proved some basic features of this family. These graphs, due to its
connection with quadratic residuosity problem on modulus of the form
pq, may find applications in topology-hiding cryptography [13]. However,
a lot of questions are still unresolved, e.g., exact automorphism group of
ΓN , a tighter bound for the domination number of ΓN etc.
Acknowledgement
The author is thankful to Avishek Adhikari of Department of Pure
Mathematics, University of Calcutta, India for some fruitful suggestions
and careful proofreading of the manuscript. The research is supported in
part by National Board of Higher Mathematics, Department of Atomic
Energy, Government of India (No 2/48(10)/2013/ NBHM(R.P.)/R&D
II/695).
References
[1] W. Ananchuen: On the adjacency properties of generalized Paley graphs, Australas.
J. Combin., 24, 129-147, 2001.
[2] W. Ananchuen and L. Caccetta: Cubic and quadruple Paley graphs with the n-e.c.
property, Discrete Math., 306, 2954-2961, 2006.
[3] R.D. Baker, G.L. Ebert, J. Hemmeter and A. Woldar: Maximal cliques in the
Paley graph of square order, J. Statist. Plann. Inference, 56(1), 33-38, 1996.
[4] S.D. Cohen: Clique Numbers of Paley Graphs, Quaest. Math., 11(2), 225-231, 1988.
[5] A. Das: Quadratic Residue Cayley Graphs on Composite Modulus, Mathematics
and Computing, Springer Proceedings in Mathematics and Statistics, Vol. 139,
2015.
[6] A.N. Elsawy: Paley graphs and their generalizations, M.S. Thesis, Heinrich Heine
University, Germany, 2009.
[7] R.E. Giudici and A.A. Olivieri: Quadratic modulo 2n Cayley graphs, Discrete
Math., 215, 73-79, Elsevier, 2000.
[8] C. Godsil and G. Royle: Algebraic Graph Theory, Graduate Texts in Mathematics,
Springer, 2001.
[9] R. Hammack, W. Imrich and S. Klavzar: Handbook of Product Graphs, Second
Edition, CRC Press, 2011.
[10] T.W. Haynes, S.T. Hedetniemi and P.J. Slater: Fundamentals of Domination in
Graphs, Marcel Dekker Inc., 1998.
[11] T.K. Lim and C.E. Praeger: On generalized Paley graphs and their automorphism
groups, Michigan Math. J., (58) 2009, 293-308.
“adm-n3” — 2019/10/20 — 9:35 — page 59 — #61
A. Das 59
[12] E. Maistrelli and D.B. Penman: Some colouring problems for Paley graph, Discrete
Math., Vol. 306, Issue 1, 99-106, 2006.
[13] T. Moran, I. Orlov and S. Richelson: Topology-Hiding Computation, Cryptology
E-print Archive, 2014. Available at http://eprint.iacr.org/2014/1022.pdf.
[14] K.H. Rosen: Elementary Number Theory and Its Applications, Addison-Wesley,
1984.
[15] D.B. West: Introduction to Graph Theory, Prentice Hall, 2001.
[16] K. Wu, W. Su, H. Luo and X. Xu: A generalization of generalized Paley graphs
and new lower bounds for R(3, q), The Electronic Journal of Combinatorics, 17
(2010).
[17] H. Zhang: Independent Sets in Direct Products of Vertex-Transitive Graphs, J.
Combin. Theory Ser. B, Vol 102, Issue 3, pg. 832-838, 2012.
Contact information
Angsuman Das Department of Mathematics,
Presidency University, Kolkata.
86/1, College Street, Kolkata 700073, India
E-Mail(s): angsuman.maths@presiuniv.ac.in
Received by the editors: 02.02.2015
and in final form 27.08.2019.
|