On Strongly Regular Graphs of Order 3(2p + 1) and 4(2p + 1) where 2p + 1 is a Prime Number

Abstract

We say that a regular graph G of order n and degree r ≥ 1 (which is not the complete graph) is strongly regular if any two distinct vertices have τ common neighbors if they are adjacent and have 𝜃 common neighbors if they are not adjacent. We here describe the parameters n,r,τ, and 𝜃 for strongly regular graphs of order 3(2p + 1) and 4(2p + 1), where 2p + 1 is a prime number.

1 Introduction

Let G be a simple graph of order n. The spectrum of G consists of the eigenvalues λ ₁ ≥ λ ₂ ≥ … ≥ λ _n of its (0, 1) adjacency matrix A and is denoted by σ(G). We say that a regular graph G of order n and degree r ≥ 1 (which is not the complete graph K _n ) is strongly regular if any two distinct vertices have τ common neighbors if they are adjacent and have 𝜃 common neighbors if they are not adjacent. Besides, we say that a regular connected graph G is strongly regular if and only if it has exactly three distinct eigenvalues [1]. Let λ ₁ = r,λ ₂ and λ ₃ denote the distinct eigenvalues of G. Let m ₁ = 1,m ₂ and m ₃ denote the multiplicity of r,λ ₂, and λ ₃, respectively. The results obtained in this work are based on the following assertion [2, 3].

Theorem 1

Let G be a connected strongly regular graph of order n and degree r. Then $m_{2}m_{3}\delta ^{2} = nr\overline r$ where δ = λ ₂ − λ ₃ and $\overline r = (n-1) - r$.

Further, let $\overline r = (n-1) - r, \overline \lambda _{2} =-\lambda _{3} - 1$, and $\overline \lambda _{3} = -\lambda _{2} - 1$ denote the distinct eigenvalues of the strongly regular graph $\overline G$, where $\overline G$ denotes the complement of G. It is known that $\overline \tau = n - 2r - 2 + \theta$ and $\overline \theta =n - 2r + \tau$ where $\overline \tau = \tau (\overline G)$ and $\overline \theta = \theta (\overline G)$.

Remark 1

(i) A strongly regular graph G of order 4n + 1 and degree r = 2n with τ = n − 1 and 𝜃 = n is called the conference graph; (ii) a strongly regular graph is the conference graph if and only if m ₂ = m ₃; and (iii) if m ₂ ≠ m ₃, then G is an integral¹ graph.

Remark 2

If G is a disconnected strongly regular graph of degree r, then G = m K _{r + 1}, where m H denotes the m-fold union of the graph H. We know that G is a disconnected strongly regular graph if and only if 𝜃 = 0.

Due to Theorem 1, we have recently obtained the following results [3]: (i) there is no strongly regular graph of order 4p + 3 if 4p + 3 is a prime number, and (ii) the only strongly regular graphs of order 4p + 1 are conference graphs if 4p + 1 is a prime number. Besides, in the same work, we have described the parameters n,r,τ, and 𝜃 for strongly regular graphs of order 2(2p + 1), where 2p + 1 is a prime number. We now proceed to establish the parameters of strongly regular graphs of order 3(2p + 1) and 4(2p + 1) where 2p + 1 is a prime number, as follows. First,

Proposition 1 (Elzinga [1])

Let G be a connected or disconnected strongly regular graph of order n and degree r. Then,

$$ r^{2} - (\tau - \theta + 1)r - (n-1)\theta = 0. $$

(1)

Proposition 2 (Elzinga [1])

Let G be a connected strongly regular graph of order n and degree r. Then,

$$ 2r + (\tau - \theta)(m_{2} + m_{3}) + \delta(m_{2} - m_{3}) = 0, $$

(2)

where δ = λ ₂ − λ ₃.

Second, in what follows, (x,y) denotes the greatest common divisor of integers $x,y\in \mathbb N$ while x∣y means that x divides y.

2 Main Results

Remark 3

In the following two Theorems 2 and 3, the complements of strongly regular graphs appear in pairs in (k ⁰) and $(\overline k^{0})$ classes, where k denotes the corresponding number of a class.

Proposition 3

Let G be a connected strongly regular graph of order 3(2p + 1) and degree r, where ² 2 p + 1 is a prime number. If p ≥ 2, then G is a conference graph if and only if δ ² = 3(2p + 1).

Proof

We note first that if G is a conference graph, then δ ² = 3(2p + 1). Conversely, let us assume that δ ² = 3(2p + 1). Since 3∤(2p + 1), it follows that δ ² is not a perfect square. Since $\delta = \lambda _{2} - \lambda _{3}\not \in \mathbb N$, it turns out that G is not integral, which proves the statement. □

Remark 4

Since the strongly regular graphs of order n = 9 are completely described, in the sequel, it will be assumed that p ≥ 2.

Proposition 4

Let G be a connected strongly regular graph of order 3(2p + 1) and degree r, where 2p + 1 is a prime number. If δ = 2p + 1, then G belongs to the class (1⁰) represented in Theorem 2.

Proof

Using Theorem 1, we have $(2p+1)m_{2}m_{3} = 3r\,\overline r$, which means that (2p + 1)∣r or $(2p+1)\mid \overline r$. Without loss of generality, we may consider only the case when (2p + 1)∣r.

Case 1

(r = 2p + 1). Then, m ₂ m ₃ = 3(4p + 1) and m ₂ + m ₃ = 6p + 2, which provides that m ₂ and m ₃ are the roots of the quadratic equation m ² − (6p + 2)m + 3(4p + 1) = 0. So we find that $m_{2},m_{3} = \frac {6p+2\pm {\Delta }}{2}$ where Δ² = (6p − 2)² − 12, a contradiction because Δ² is not a perfect square for p ≥ 2.

Case 2

(r = 2(2p + 1)). Then m ₂ m ₃ = 12p which yields that m ₂ = 6p and m ₃ = 2 or m ₂ = 2 and m ₃ = 6p. Consider first the case when m ₂ = 6p and m ₃ = 2. Using (2), we obtain τ − 𝜃 = −(2p + 1). Since $\lambda _{2,3} =\frac {\tau - \theta \pm \delta }{2}$, we get easily λ ₂ = 0 and λ ₃ = − (2p + 1), which proves that G is the strongly regular graph $\overline {3K_{2p+1}}$ of degree r = 4p + 2 with τ = 2p + 1 and 𝜃 = 4p + 2. Consider the case when m ₂ = 2 and m ₃ = 6p. Using (2), we obtain $\tau - \theta = \frac {3(p-1)(2p+1)}{3p+1}$, a contradiction because (3p + 1)∤3(p − 1).

□

Proposition 5

There is no connected strongly regular graph G of order 3(2p + 1) and degree r with δ = 2(2p + 1), where 2p + 1 is a prime number.

Proof

Contrary to the statement, assume that G is a strongly regular graph with δ = 2(2p + 1). Using Theorem 2, we have $4(2p+1)m_{2}m_{3} = 3r\,\overline r$ which means that (2p + 1)∣r or $(2p+1)\mid \overline r$. Consider the case when r = 2p + 1 and $\overline r = 4p+1$. Then , 4m ₂ m ₃ = 3(4p + 1), a contradiction because 4∤(4p + 1). Consider the case when r = 2(2p + 1) and $\overline r = 2p$. Then, m ₂ + m ₃ = 6p + 2 and m ₂ m ₃ = 3p, a contradiction. □

Proposition 6

Let G be a connected strongly regular graph of order 3(2p + 1) and degree r, where 2p + 1 is a prime number. If m ₂ = 2p + 1 and m ₃ = 4 p + 1, then G belongs to the class (6⁰) or $(\overline 7^{0})$ represented in Theorem 2.

Proof

Using (2), we obtain p δ = r + (τ − 𝜃)(3p + 1). Since δ = λ ₂ − λ ₃ and τ − 𝜃 = λ ₂ + λ ₃, we arrive at 2p(2|λ ₃| − λ ₂) = τ − 𝜃 + r. Since r ≤ 6p + 1,𝜃 ≤ r and τ < r, it follows that 0 ≤ τ − 𝜃 + r ≤ 12p. Let 2|λ ₃| − λ ₂ = t where t = 0, 1,…,6. Let λ ₃ = −k where k is a positive integer. Then (i) λ ₂ = 2k − t; (ii) τ − 𝜃 = k − t; (iii) δ = 3k − t; and (iv) r = (2p + 1)t − k. Since δ ² = (τ − 𝜃)² + 4(r − 𝜃) (see [1]), we obtain (v) 𝜃 = (2p + 1)t − (2k ² − (t − 1)k). Using (ii), (iv), and (v), it is not difficult to see that (1) is transformed into

$$ 2(p+1)t^{2} - 3(2p+1)t + 6k^{2} - 3k(2t-1) = 0. $$

(3)

Case 1

(t = 0). Using (i), (ii), (iii), and (iv), we find that λ ₂ = 2k and λ ₃ = − k,τ − 𝜃 = k, δ = 3k, and r = − k, a contradiction.

Case 2

(t = 1). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = 2k − 1 and λ ₃ = − k, τ − 𝜃 = k − 1,δ = 3k − 1,r = (2p + 1)−k, and 𝜃 = (2p + 1)−2k ². Using (3), we find that 4p + 1=3k(2k − 1). Replacing k with 4k − 1, we arrive at p = 24k ² − 15k + 2, where k is a positive integer. So we obtain that G is a strongly regular graph of order 3(48k ² − 30k + 5) and degree r = 2(3k − 1)(8k − 3) with τ = (2k − 1)(8k − 1) and 𝜃 = (2k − 1)(8k − 3).

Case 3

(t = 2). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = 2(k − 1) and λ ₃ = − k, τ − 𝜃 = k − 2,δ = 3k − 2,r = 2(2p + 1)−k, and 𝜃 = 2(2p + 1)−(2k ² − k). Using (3), we find that 4p + 1=3(k − 1)(2k − 1). Replacing k with 4k + 2, we arrive at p = 24k ² + 15k + 2, where k is a non-negative integer. So we obtain that G is a strongly regular graph of order 3(48k ² + 30k + 5) and degree r = 8(3k + 1)(4k + 1) with τ = 4(4k + 1)² + 4k and 𝜃 = 4(4k + 1)².

Case 4

(t = 3). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = 2k − 3 and λ ₃ = − k, τ − 𝜃 = k − 3,δ = 3(k − 1),r = 3(2p + 1)−k, and 𝜃 = 3(2p + 1)−(2k ² − 2k). Using (3), we find that (k − 1)(2k − 3) = 0. So we obtain that G is the complete graph, a contradiction.

Case 5

(t = 4,5,6). Using (3), we find that (x) 8p + 6k ² − 21k + 20=0; (y) 20p + 6k ² − 27k + 35=0 and (z) 12p + 2k ² − 11k + 18=0 for t = 4,t = 5 and t = 6, respectively, a contradiction.

□

Proposition 7

Let G be a connected strongly regular graph of order 3(2p + 1) and degree r, where 2p + 1 is a prime number. If m ₂ = 2(2p + 1) and m ₃ = 2p, then G belongs to the class (2⁰) or (4⁰) or $(\overline 5^{0})$ represented in Theorem 2.

Proof

Using (2), we obtain 2p(|λ ₃|−2λ ₂) = (τ − 𝜃)+δ + r. Since (τ − 𝜃)+δ = 2λ ₂ and $\lambda _{2} \le \lfloor \frac {6p+3}{2}\rfloor - 1$ (see [3]), it follows that 0<(τ − 𝜃)+δ + r ≤ 12p. Let |λ ₃|−2λ ₂ = t where t = 1,2,…,6. Let λ ₂ = k where k is a non-negative integer. Then (i) λ ₃ = − (2k + t); (ii) τ − 𝜃 = − (k + t); (iii) δ = 3k + t; (iv) r = 2(p t − k); and (v) 𝜃 = 2p t − (2k ² + (t + 2)k). Using (ii), (iv), and (v), we can easily see that (1) is transformed into

$$\label {T02} t(t-3)p + 3k(k+1) = 0. $$

(4)

Case 1

(t = 1). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − (2k + 1), τ − 𝜃 = − (k + 1),δ = 3k + 1,r = 2(p − k), and 𝜃 = 2p − (2k ² + 3k). Using (4), we find that 2p = 3k(k + 1). So we obtain that G is a strongly regular graph of order 3(3k ² + 3k + 1) and degree r = k(3k + 1) with τ = k ² − k − 1 and 𝜃 = k ², where k ≥ 2.

Case 2

(t = 2). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − 2(k + 1), τ − 𝜃 = − (k + 2),δ = 3k + 2,r = 2(2p − k), and 𝜃 = 4p − (2k ² + 4k). Using (4), we find that 2p = 3k(k + 1). So we obtain that G is a strongly regular graph of order 3(3k ² + 3k + 1) and degree r = 2k(3k + 2) with τ = 4k ² + k − 2 and 𝜃 = 2k(2k + 1).

Case 3

(t = 3). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − (2k + 3), τ − 𝜃 = − (k + 3),δ = 3(k + 1),r = 2(3p − k), and 𝜃 = 6p − (2k ² + 5k). Using (4), we find that k(k + 1) = 0. So we obtain that G is a strongly regular graph $\overline {(2p+1)K_{3}}$ of degree r = 6p with τ = 6p − 3 and 𝜃 = 6p.

Case 4

(t = 4, 5, 6). Using (4), we find that (x) 4p + 3k ² + 3k = 0; (y) 10p + 3k ² + 3k = 0 and (z) 6p + k ² + k = 0 for t = 4,t = 5 and t = 6, respectively, a contradiction.

□

Proposition 8

Let G be a connected strongly regular graph of order 3(2p + 1) and degree r, where 2p + 1 is a prime number. If m ₃ = 2p + 1 and m ₂ = 4p + 1, then G belongs to the class $(\overline 6^{0})$ or (7⁰) represented in Theorem 2.

Proof

Using (2), we obtain 2p(|λ ₃|−2λ ₂) = τ − 𝜃 + r. Let |λ ₃|−2λ ₂ = t where t = 0,1,…,6. Let λ ₂ = k where k is a non-negative integer. Then, (i) λ ₃ = − (2k + t); (ii) τ − 𝜃 = − (k + t); (iii) δ = 3k + t; (iv) r = (2p + 1)t + k; and (v) 𝜃 = (2p + 1)t − (2k ² + (t − 1)k). Using (ii), (iv), and (v), we can easily see that (1) is reduced to

$$\label {T03} 2(p+1)t^{2} - 3(2p+1)t + 6k^{2} + 3k(2t-1) = 0. $$

(5)

Case 1

(t = 0). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − 2k,τ − 𝜃 = − k,δ = 3k,r = k and 𝜃 = − k(2k − 1), a contradiction.

Case 2

(t = 1). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − (2k + 1), τ − 𝜃 = − (k + 1), δ = 3k + 1, r = (2p + 1) +k, and 𝜃 = (2p + 1) −2k ². Using (5), we find that 4p + 1 = 3k(2k + 1). Replacing k with 4k + 1, we arrive at p = 24k ² + 15k + 2, where k is a non-negative integer. So we obtain that G is a strongly regular graph of order 3(48k ² + 30k + 5) and degree r = 2(3k + 1)(8k + 3) with τ = (2k + 1)(8k + 1) and 𝜃 = (2k + 1)(8k + 3).

Case 3

(t = 2). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − 2(k + 1), τ − 𝜃 = − (k + 2),δ = 3k + 2,r = 2(2p + 1)+k, and 𝜃 = 2(2p + 1)−(2k ² + k). Using (5), we find that 4p + 1=3(k + 1)(2k + 1). Replacing k with 4k − 2, we arrive at p = 24k ² − 15k + 2, where k is a positive integer. So we obtain that G is a strongly regular graph of order 3(48k ² − 30k + 5) and degree r = 8(3k − 1)(4k − 1) with τ = 4(4k − 1)² − 4k and 𝜃 = 4(4k − 1)².

Case 4

(t = 3, 4, 5, 6). Using (5), we find that (x) 2k ² + 5k + 3 = 0; (y) 8p + 6k ² + 21k + 20 = 0; (z) 20p + 6k ² + 27k + 35 = 0 and (w) 12p + 2k ² + 11k + 18 = 0 for t = 3, 4, 5, 6, respectively, a contradiction.

□

Proposition 9

Let G be a connected strongly regular graph of order 3(2p + 1) and degree r, where 2p+1 is a prime number. If m ₃ = 2(2p + 1) and m ₂ = 2p, then G belongs to the class $(\overline 4^{0})$ or (5⁰) represented in Theorem 2.

Proof

Using (2), we obtain 2p(2|λ ₃| − λ ₂) = (τ − 𝜃) − δ + r. Since (τ − 𝜃) − δ = 2λ ₃ and $|\lambda _{3}| \le \lfloor \frac {6p+3}{2}\rfloor$ (see [3]), it follows that −6p ≤ (τ − 𝜃) − δ + r ≤ 6p. Let 2|λ ₃| − λ ₂ = t where t = 0,±1,±2,±3. Let λ ₃ = − k where k is a positive integer. Then (i) λ ₂ = 2k − t; (ii) τ − 𝜃 = k − t; (iii) δ = 3k − t; (iv) r = 2(p t + k); and (v) 𝜃 = 2p t − (2k ² − (t + 2)k). Using (ii), (iv), and (v), we can easily see that (1) is reduced to

$$\label {T04} t(t-3)p + 3k(k-1) = 0. $$

(6)

Case 1

(t = 0). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = 2k and λ ₃ = − k, τ − 𝜃 = k, δ = 3k,r = 2k, and 𝜃 = − 2k ² + 2k. Using (6), we find that k(k − 1) = 0. So we obtain that G is disconnected, a contradiction.

Case 2

(t = 1). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = 2k − 1 and λ ₃ = − k, τ − 𝜃 = k − 1,δ = 3k − 1,r = 2(p + k), and 𝜃 = 2p − (2k ² − 3k). Using (6), we find that 2p = 3k(k − 1). Replacing k with k + 1, we obtain that G is a strongly regular graph of order 3(3k ² + 3k + 1) and degree r = (k + 1)(3k + 2) with τ = (k + 1)² + k and 𝜃 = (k + 1)².

Case 3

(t = 2). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = 2(k − 1) and λ ₃ = − k, τ − 𝜃 = k − 2,δ = 3k − 2,r = 2(2p + k), and 𝜃 = 4p − (2k ² − 4k). Using (6), we find that 2p = 3k(k − 1). Replacing k with k + 1, we obtain that G is a strongly regular graph of order 3(3k ² + 3k + 1) and degree r = 2(k + 1)(3k + 1) with τ = 4k ² + 7k + 1 and 𝜃 = 2(k + 1)(2k + 1), where ³ k ≥ 2.

Case 4

(t = 3). Using (i), (ii), (iii), (iv) and (v) we find that λ ₂ = 2k − 3 and λ ₃ = − k, τ − 𝜃 = k − 3,δ = 3(k − 1),r = 2(3p + k), and 𝜃 = 6p − (2k ² − 5k). Using (6) we find that k(k − 1) = 0. So we obtain that G is the complete graph, a contradiction.

Case 5

(t = −1,−2,−3). Using (v), we find that (x) 𝜃 = −2p − 2k ² + k; (y) 𝜃 = −4p − 2k ²; and (z) 𝜃 = −6p − 2k ² − k for t = −1,t = −2, and t = −3, respectively, a contradiction.

□

Theorem 2

Let G be a connected strongly regular graph of order 3(2p +1) and degree r, where 2p + 1 is a prime number. Then G is one of the following strongly regular graphs:

• (1⁰) G is the strongly regular graph $\overline {3K_{2p+1}}$ of order n = 3(2p + 1) and degree r = 4p + 2 with τ = 2p + 1 and 𝜃= 4p + 2, where $p\in \mathbb N$ and 2 p + 1 is a prime number. Its eigenvalues are λ ₂ = 0 and λ ₃ = −(2p + 1) with m ₂ = 6p and m ₃ = 2;

• (2⁰) G is the strongly regular graph $\overline {(2p+1)K_{3}}$ of order n = 3(2p + 1) and degree r = 6p with τ = 6p −3 and𝜃= 6p, where $p\in \mathbb N$ and 2p + 1 is a prime number. Its eigenvalues are λ ₂ = 0 and λ ₃ = −3 with m ₂ = 2(2p + 1) and m ₃ = 2p;

• (3⁰) G is the conference graph of order n = 3(4k − 1) and degree r = 6k − 2 with τ = 3k − 2 and𝜃= 3k − 1, where $k\in \mathbb N$ and 4k − 1 is a prime number. Its eigenvalues are $\lambda _{2} = \frac {-1 + \sqrt {3(4k-1)}}{2}$ and $\lambda _{3} =\frac {-1 - \sqrt {3(4k-1)}}{2}$ with m ₂ = 6k − 2 and m ₃ = 6k − 2;

• (4⁰) G is the strongly regular graph of order n = 3(3k ² + 3k + 1) and degree r = k(3k + 1) with τ = k ² − k − 1 and𝜃= k ², where k ≥ 2 and 3k ² + 3k + 1 is a prime number. Its eigenvalues are λ ₂ = k and λ ₃ = −(2k + 1) with m ₂ = 2(3k ² + 3k + 1) and m ₃ = 3 k(k + 1);

• $(\overline 4^{0})$  G is the strongly regular graph of order n = 3(3k ² + 3k + 1) and degree r = 2(k + 1)(3k + 1) with τ = 4k ² + 7k + 1 and𝜃= 2(k + 1)(2k + 1), where k ≥ 2 and 3k ² + 3k + 1 is a prime number. Its eigenvalues are λ ₂ = 2k and λ ₃ = −(k + 1) with m ₂ = 3k(k + 1) and m ₃ = 2(3k ² + 3k + 1);

• (5⁰) G is the strongly regular graph of order n = 3(3k ² + 3k + 1) and degree r = (k + 1)(3k + 2) with τ = (k + 1)² + k and = (k + 1)², where $k\in \mathbb N$ and 3k ² + 3k + 1 is a prime number. Its eigenvalues are λ ₂ = 2k + 1 and λ ₃ = −(k + 1) with m ₂ = 3k(k + 1) and m ₃ = 2(3k ² + 3k + 1);

• $(\overline 5^{0})$  G is the strongly regular graph of order n = 3(3k ² + 3k + 1) and degree r = 2k(3k + 2) with τ = 4k ² + k − 2 and = 2k(2k + 1), where $k\in \mathbb N$ and 3k ² + 3k + 1 is a prime number. Its eigenvalues are λ ₂ = k and λ ₃ = −2(k + 1) with m ₂ = 2(3k ² + 3k + 1) and m ₃ = 3k(k + 1);

• (6⁰) G is the strongly regular graph of order n = 3(48k ² − 30k + 5) and degree r = 2(3k − 1)(8k − 3) with τ = (2k − 1)(8k − 1) and 𝜃= (2k − 1)(8k − 3), where $k\in \mathbb N$ and 48k ² − 30k + 5 is a prime number. Its eigenvalues are λ ₂ = 8k − 3 and λ ₃ = −(4k − 1) with m ₂ = 48k ² − 30k + 5 and m ₃ = 3(4k − 1)(8k − 3);

• $(\overline 6^{0})$  G is the strongly regular graph of order n = 3(48k ² − 30k + 5) and degree r = 8(3k − 1)(4k − 1) with τ = 4(4k − 1)² − 4k and𝜃= 4(4k − 1)², where $k\in \mathbb N$ and 48k ² − 30k + 5 is a prime number. Its eigenvalues are λ ₂ = 4k − 2 and λ ₃ = −2(4k − 1) with m ₂ = 3(4k − 1)(8k − 3) and m ₃ = 48k ² − 30k + 5;

• (7⁰) G is the strongly regular graph of order n = 3(48k ² + 30k + 5) and degree r = 2(3k + 1)(8k + 3) with τ = (2k + 1)(8k + 1) and𝜃= (2k + 1)(8k + 3), where k ≥ 0 and 48k ² + 30k + 5 is a prime number. Its eigenvalues are λ ₂ = 4k + 1 and λ ₃ = −(8k + 3) with m ₂ = 3(4k + 1)(8k + 3) and m ₃ = 48k ² + 30k + 5;

• $(\overline 7^{0})$  G is the strongly regular graph of order n = 3(48k ² + 30k + 5) and degree r = 8(3k + 1)(4k + 1) with τ = 4(4k + 1)² + 4k and = 4(4k + 1)², where k ≥ 0 and 48k ² + 30k + 5 is a prime number. Its eigenvalues are λ ₂ = 2(4k + 1) and λ ₃ = −(4k + 2) with m ₂ = 48k ² + 30k + 5 and m ₃ = 3(4k + 1)(8k + 3).

Proof

We note first that if G is a strongly regular graph with δ ² = 3(2p + 1), according to Proposition 3, it belongs to the class (3⁰). Consequently, assume that G is an integral (non-conference) strongly regular graph. Using Theorem 1, we have $m_{2}m_{3} \delta ^{2} = 3(2p+1)r\,\overline r$. We shall now consider the following three cases.

Case 1

((2p + 1)∣δ ²). In this case, (2p + 1)∣δ because G is an integral graph. Since δ = λ ₂ + |λ ₃|<6p + 3 (see [3]), it follows that δ = 2p + 1 or δ = 2(2p + 1). Using Propositions 4 and 5, it turns out that G belongs to the class (1⁰).

Case 2

((2p + 1)∣m ₂). Since m ₂ + m ₃ = 6p + 2, it follows that m ₂ = 2p + 1 and m ₃ = 4p + 1 or m ₂ = 2(2p + 1) and m ₃ = 2p. Using Propositions 6 and 7, it turns out that G belongs to the class (2⁰) or (4⁰) or $(\overline 5^{0})$ or (6⁰) or $(\overline 7^{0})$.

Case 3

((2p + 1)∣m ₃). Since m ₃ + m ₂ = 6p + 2, it follows that m ₃ = 2p + 1 and m ₂ = 4p + 1 or m ₃ = 2(2p + 1) and m ₂ = 2p. Using Propositions 8 and 9, it turns out that G belongs to the class $(\overline 4^{0})$ or (5⁰) or $(\overline 6^{0})$ or (7⁰).

□

Proposition 10

Let G be a connected strongly regular graph of order 4(2p + 1) and degree r, where 2p + 1 is a prime number. If δ = 2p + 1, then G belongs to the class (2⁰) represented in Theorem 3.

Proof

Using Theorem 1, we have $(2p+1)m_{2}m_{3} = 4r\,\overline r$, which means that (2p + 1)∣r or $(2p+1)\mid \overline r$. It is sufficient to consider only the case when (2p + 1)∣r.

Case 1

(r = 2p + 1). Then, m ₂ m ₃ = 8(3p + 1) and m ₂ + m ₃ = 8p + 3. So we find that $m_{2},m_{3} = \frac {8p+3\pm {\Delta }}{2}$ where Δ² = (8p − 3)² − 32, a contradiction because Δ² is not a perfect square.

Case 2

(r = 2(2p + 1)). Then m ₂ m ₃ = 8(4p + 1) which yields that $m_{2},m_{3} = \frac {8p+3\pm {\Delta }}{2}$ where Δ² = (8p − 3)² − 32(p + 1) and Δ² = (8p − 6)² + 16p − 59. We can easily verify that Δ² = −39,73,313 for p = 1,2,3, respectively. Since Δ² is not a perfect square for p = 1,2,3, we can assume p ≥ 4. So we obtain (8p − 6)<Δ<(8p − 3) for p ≥ 4, which provides that Δ=8p − 5. Using this fact, we find that m ₂ = 8p − 1 and m ₃ = 4 or m ₂ = 4 and m ₃ = 8p − 1. Thus, we have 4(8p − 1) = 8(4p + 1), a contradiction.

Case 3

(r = 3(2p + 1)). In this situation, m ₂ m ₃ = 24p and m ₂ + m ₃ = 8p + 3, which yields that m ₂ = 8p and m ₃ = 3 or m ₂ = 3 and m ₃ = 8p. Consider first the case when m ₂ = 8p and m ₃ = 3. Using (2), we obtain τ − 𝜃 = − (2p + 1). Since $\lambda _{2,3} = \frac {(\tau -\theta )\pm \delta }{2}$, we get easily λ ₂ = 0 and λ ₃ = − (2p + 1), which proves that G is the strongly regular graph $\overline {4K_{2p+1}}$ of degree r = 6p + 3 with τ = 4p + 2 and 𝜃 = 6p + 3. Consider the case when m ₂ = 3 and m ₃ = 8p. Using (2), we obtain $\tau - \theta = \frac {(2p+1)(8p-9)}{8p+3}$, a contradiction because (8p + 3)∤(8p − 9).

□

Proposition 11

Let G be a connected strongly regular graph of order 4(2p + 1) and degree r, where 2p + 1 is a prime number. If δ = 2(2p + 1), then G belongs to the class (1⁰) represented in Theorem 3.

Proof

Using Theorem 1, we have $(2p+1)m_{2}m_{3} = r\,\overline r$, which means that (2p + 1)|r or $(2p+1)\mid \overline r$. We shall here consider only the case when (2p + 1)∣r.

Case 1

(r = 2p + 1). In this situation, we have m ₂ m ₃ = 6p + 2 and m ₂ + m ₃ = 8p + 3, a contradiction.

Case 2

(r = 2(2p + 1)). Then, m ₂ m ₃ = 8p + 2 and m ₂ + m ₃ = 8p + 3, which means that m ₂ = 8p + 2 and m ₃ = 1 or m ₂ = 1 and m ₃ = 8p + 2. Consider first the case when m ₂ = 8p + 2 and m ₃ = 1. Using (2), we obtain easily τ − 𝜃 = − 2(2p + 1), which provides that λ ₂ = 0 and λ ₃ = − 2(2p + 1). So we obtain that G is the complete bipartite graph K _{4p + 2,4p + 2} of degree r = 2(2p + 1) with τ = 0 and 𝜃 = 2(2p + 1). Consider the case when m ₂ = 1 and m ₃ = 8p + 2. Using (2), we obtain $\tau - \theta = \frac {2(2p+1)(8p-1)}{8p+3}$, a contradiction because (8p + 3)∤(8p − 1).

Case 3

(r = 3(2p + 1)). In this situation, we have m ₂ m ₃ = 6p and m ₂ + m ₃ = 8p + 3, a contradiction.

□

Proposition 12

There is no connected strongly regular graph G of order 4(2p + 1) and degree r with δ = 3(2p + 1), where 2p +1 is a prime number.

Proof

Contrary to the statement, assume that G is a strongly regular graph with δ = 3(2p + 1). Using Theorem 2, we have $9(2p+1)m_{2}m_{3} = 4r\,\overline r$. Consider first the case when r = 2p + 1 and $\overline r = 6p+2$. Then, 9m ₂ m ₃ = 8(3p + 1) and 9(m ₂ + m ₃) = 9(8p + 3), a contradiction. Consider the case when r = 2(2p + 1) and $\overline r = 4p+1$. Then 9m ₂ m ₃ = 8(4p + 1) and 9(m ₂ + m ₃) = 9(8p + 3), a contradiction. Consider the case when r = 3(2p + 1) and $\overline r = 2p$. Then 3m ₂ m ₃ = 8p and m ₂ + m ₃ = 8p + 3, a contradiction. □

Proposition 13

Let G be a connected strongly regular graph of order 4(2p + 1) and degree r, where 2p + 1 is a prime number. If m ₂ = 2p + 1 and m ₃ = 6p + 2, then G belongs to the class (6⁰) or $(\overline 7^{0})$ or (8⁰ ) represented in Theorem 3.

Proof

Using (2), we obtain 4p(3|λ ₃| − λ ₂) = 3(τ − 𝜃) − δ + 2r. Since 3(τ − 𝜃) − δ = 2λ ₂ + 4λ ₃, it follows that −16p ≤ 3(τ − 𝜃) − δ + 2r ≤ 24p. Let 3|λ ₃| − λ ₂ = t where −4 ≤ t ≤ 6. Let λ ₃ = −k where k is a positive integer. Then (i) λ ₂ = 3k − t; (ii) τ − 𝜃 = 2k − t; (iii) δ = 4k − t; (iv) r = (2p + 1)t − k; and (v) 𝜃 = (2p + 1)t − (3k ² − (t − 1)k). Using (ii), (iv), and (v), we can easily see that (1) is reduced to

$$\label {T05} (p+1)t^{2} - 2(2p+1)t + 6k^{2} - 2k(2t-1) = 0. $$

(7)

Case 1

(t = 0). Using (i), (ii), (iii), and (iv), we find that λ ₂ = 3k and λ ₃ = − k,τ − 𝜃 = k, δ = 4k, and r = − k, a contradiction.

Case 2

(t = 1). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = 3k − 1 and λ ₃ = − k, τ − 𝜃 = 2k − 1,δ = 4k − 1,r = (2p + 1)−k, and 𝜃 = (2p + 1)−3k ². Using (7), we find that 3p + 1=2k(3k − 1). Replacing k with 3k + 1, we arrive at p = 18k ² + 10k + 1, where k is a positive integer. So we obtain that G is a strongly regular graph of order 4(36k ² + 20k + 3) and degree r = (4k + 1)(9k + 2) with τ = 9k ² + 8k + 1 and 𝜃 = k(9k + 2).

Case 3

(t = 2). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = 3k − 2 and λ ₃ = − k, τ − 𝜃 = 2(k − 1),δ = 2(2k − 1),r = 2(2p + 1)−k, and 𝜃 = 2(2p + 1)−(3k ² − k). Using (7), we find that 2p = 3k(k − 1). Replacing k with k + 1, we obtain that G is a strongly regular graph of order 4(3k ² + 3k + 1) and degree r = (2k + 1)(3k + 1) with τ = 3k(k + 1) and 𝜃 = k(3k + 1).

Case 4

(t = 3). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = 3(k − 1) and λ ₃ = − k, τ − 𝜃 = 2k − 3,δ = 4k − 3,r = 3(2p + 1)−k, and 𝜃 = 3(2p + 1)−(3k ² − 2k). Using (7), we find that 3p − 3=2k(3k − 5). Replacing k with 3k, we arrive at p = 18k ² − 10k + 1, where k is a positive integer. So we obtain that G is a strongly regular graph of order 4(36k ² − 20k + 3) and degree r = 9(3k − 1)(4k − 1) with τ = 9(3k − 1)² + 3(2k − 1) and 𝜃 = 9(3k − 1)².

Case 5

(t = 4). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = 3k − 4 and λ ₃ = − k, τ − 𝜃 = 2(k − 2),δ = 4(k − 1),r = 4(2p + 1)−k, and 𝜃 = 4(2p + 1)−(3k ² − 3k). Using (7), we find that (k − 1)(3k − 4) = 0. So we obtain that G is the complete graph, a contradiction.

Case 6

(t = 5 and t = 6). Using (7), we find that 5p + 6k ² − 18k + 15=0 and 6p + 3k ² − 11k + 12=0 for t = 5 and t = 6, respectively, a contradiction.

Case 7

(t ≤ −1). Using (7), we find that (p + 1)t ² + 2|t|(2p + 1)+6k ² + 2k(2|t|+1) = 0, a contradiction.

□

Proposition 14

Let G be a connected strongly regular graph of order 4(2p + 1) and degree r, where 2p + 1 is a prime number. If m ₂ = 2(2p + 1) and m ₃ = 4p + 1, then G belongs to the class (4⁰) represented in Theorem 3.

Proof

Using (2), we obtain 8p(|λ ₃| − λ ₂) = 3(τ − 𝜃)+δ + 2r. Since 3(τ − 𝜃)+δ = 4λ ₂ + 2λ ₃, it follows that −8p ≤ 3(τ − 𝜃)+δ + 2r ≤ 32p. Let |λ ₃| − λ ₂ = t where −1 ≤ t ≤ 4. Let λ ₂ = k where k is a non-negative integer. Then (i) λ ₃ = − (k + t); (ii) τ − 𝜃 = − t; (iii) δ = 2k + t; (iv) r = (4p + 1)t − k; and (v) 𝜃 = (4p + 1)t − (k ² + (t + 1)k). Using (ii), (iv), and (v), we can easily see that (1) is reduced to

$$\label {T06} t(t-2)(4p+1) + 2k(k+1) = 0. $$

(8)

Case 1

(t = 0). Using (i), (ii), (iii), and (iv), we find that λ ₂ = k and λ ₃ = − k,τ − 𝜃 = 0, δ = 2k, and r = − k, a contradiction.

Case 2

(t = 1). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − (k + 1), τ − 𝜃 = − 1,δ = 2k + 1,r = (4p + 1)−k, and 𝜃 = (4p + 1)−(k ² + 2k). Using (8), we find that 4p + 1=2k(k + 1), a contradiction because 2∤(4p + 1).

Case 3

(t = 2). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − (k + 2), τ − 𝜃 = − 2,δ = 2(k + 1),r = 2(4p + 1)−k, and 𝜃 = 2(4p + 1)−(k ² + 3k). Using (8), we find that k(k + 1) = 0. So we obtain that G is the cocktail-party graph $\overline {(4p+2)K_{2}}$ of degree r = 8p + 2 with τ = 8p and 𝜃 = 8p + 2.

Case 4

(t = 3,4 and t = −1). Using (8), we find that (x) 3(4p + 1)+2k(k + 1) = 0; (y) 4(4p + 1)+k(k + 1) = 0 and (z) 3(4p + 1)+2k(k + 1) = 0 for t = 3,t = 4 and t = −1 respectively, a contradiction.

□

Proposition 15

Let G be a connected strongly regular graph of order 4(2p + 1) and degree r, where 2p + 1 is a prime number. If m ₂ = 3(2p + 1) and m ₃ = 2p, then G belongs to the class (3⁰) or (5⁰) represented in Theorem 3.

Proof

Using (2), we obtain 4p(|λ ₃|−3λ ₂) = 3(τ − 𝜃)+3δ + 2r. Since 3(τ − 𝜃)+3δ = 6λ ₂, it follows that 0<3(τ − 𝜃)+3δ + 2r ≤ 40p. Let |λ ₃|−3λ ₂ = t where t = 1,2,…,10. Let λ ₂ = k where k is a non-negative integer. Then (i) λ ₃ = − (3k + t); (ii) τ − 𝜃 = − (2k + t); (iii) δ = 4k + t; (iv) r = 2p t − 3k; and (v) 𝜃 = 2p t − (3k ² + (t + 3)k). Using (ii), (iv), and (v), we can easily see that (1) is reduced to

$$\label {T07} t(t-4)p + 6k(k+1) = 0. $$

(9)

Case 1

(t = 1). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − (3k + 1),τ − 𝜃 = − (2k + 1),δ = 4k + 1,r = 2p − 3k, and 𝜃 = 2p − (3k ² + 4k). Using (9), we find that p = 2k(k + 1) which yields that 2p + 1=(2k + 1)², a contradiction.

Case 2

(t = 2). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − (3k + 2), τ − 𝜃 = − 2(k + 1),δ = 2(2k + 1),r = 4p − 3k, and 𝜃 = 4p − (3k ² + 5k). Using (9), we find that 2p = 3k(k + 1), where k is a positive integer. So we obtain that G is a strongly regular graph of order 4(3k ² + 3k + 1) and degree r = 3k(2k + 1) with τ = 3k ² − k − 2 and 𝜃 = k(3k + 1).

Case 3

(t = 3). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − 3(k + 1), τ − 𝜃 = − (2k + 3),δ = 4k + 3,r = 3(2p − 1), and 𝜃 = 6p − (3k ² + 6k). Using (9), we find that p = 2k(k + 1) which yields that 2p + 1=(2k + 1)², a contradiction.

Case 4

(t = 4). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − (3k + 4), τ − 𝜃 = − 2(k + 2),δ = 4(k + 1),r = 8p − 3k, and 𝜃 = 8p − (3k ² + 7k). Using (9), we find that k(k + 1) = 0. So we obtain that G is the strongly regular graph $\overline {(2p+1)K_{4}}$ of degree r = 8p with τ = 8p − 4 and 𝜃 = 8p.

Case 5

(t ≥ 5). In this case, we find that t(t − 4)p + 6k(k + 1) = 0, a contradiction (see (9)).

□

Proposition 16

Let G be a connected strongly regular graph of order 4(2p + 1) and degree r, where 2p + 1 is a prime number. If m ₃ = 2p + 1 and m ₂ = 6p + 2, then G belongs to the class $(\overline 6^{0})$ or (7⁰) or $(\overline 8^{0})$ represented in Theorem 3.

Proof

Using (2) we obtain 4p(|λ ₃|−3λ ₂) = 3(τ − 𝜃)+δ + 2r. Let |λ ₃|−3λ ₂ = t where −2 ≤ t ≤ 8. Let λ ₂ = k where k is a non-negative integer. Then (i) λ ₃ = − (3k + t); (ii) τ − 𝜃 = − (2k + t); (iii) δ = 4k + t; (iv) r = (2p + 1)t + k and (v) 𝜃 = (2p + 1)t − (3k ² + (t − 1)k). Using (ii), (iv) and (v) we can easily see that (1) is reduced to

$$ \label {T08} (p+1)t^{2} - 2(2p+1)t + 6k^{2} + 2k(2t-1) = 0. $$

(10)

Case 1

(t = 0). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − 3k, τ − 𝜃 = − 2k, δ = 4k,r = k, and 𝜃 = − k(3k − 1), which provides that 𝜃 = 0. So we obtain that G is disconnected, a contradiction.

Case 2

(t = 1). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − (3k + 1), τ − 𝜃 = − (2k + 1),δ = 4k + 1,r = (2p + 1)+k, and 𝜃 = (2p + 1)−3k ². Using (10) we find that 3p + 1=2k(3k + 1). Replacing k with 3k − 1, we arrive at p = 18k ² − 10k + 1, where k is a positive integer. So we obtain that G is a strongly regular graph of order 4(36k ² − 20k + 3) and degree r = (4k − 1)(9k − 2) with τ = 9k ² − 8k + 1 and 𝜃 = k(9k − 2).

Case 3

(t = 2). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − (3k + 2), τ − 𝜃 = − 2(k + 1),δ = 2(2k + 1),r = 2(2p + 1)+k, and 𝜃 = 2(2p + 1)−(3k ² + k). Using (10), we find that 2p = 3k(k + 1), where k is a positive integer. So we obtain that G is a strongly regular graph of order 4(3k ² + 3k + 1) and degree r = (2k + 1)(3k + 2) with τ = 3k(k + 1) and 𝜃 = (k + 1)(3k + 2).

Case 4

(t = 3). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = −3(k + 1), τ − 𝜃 = − (2k + 3),δ = 4k + 3,r = 3(2p + 1)+k, and 𝜃 = 3(2p + 1)−(3k ² + 2k). Using (10), we find that 3p − 3=2k(3k + 5). Replacing k with 3k, we arrive at p = 18k ² + 10k + 1, where k is a positive integer. So we obtain that G is a strongly regular graph of order 4(36k ² + 20k + 3) and degree r = 9(3k + 1)(4k + 1) with τ = 9(3k + 1)² − 3(2k + 1) and 𝜃 = 9(3k + 1)².

Case 5

(t ≥ 4). Using (i), (ii), (iii), and (iv), we find that λ ₂ = k and λ ₃ = − (3k + 4), τ − 𝜃 = − 2(k + 2),δ = 4(k + 1), and r = 4(2p + 1)+k ≥ 8p + 4, a contradiction.

Case 6

(t = −1,−2). Using (10), we obtain (p + 1)t ² + 2|t|(2p + 1)+6k ² − 2k(2|t|+1) = 0, a contradiction.

□

Proposition 17

There is no connected strongly regular graph G of order 4(2p + 1) and degree r with m ₃ = 2(2p +1) and m ₂ = 4p + 1, where 2p + 1 is a prime number.

Proof

Contrary to the statement, assume that G is a strongly regular graph with m ₃ = 2(2p + 1) and m ₂ = 4p + 1. Using (2), we obtain 8p(|λ ₃| − λ ₂) = 3(τ − 𝜃) − δ + r. Let |λ ₃| − λ ₂ = t where −2 ≤ t ≤ 3. Let λ ₂ = k where k is a non-negative integer. Then (i) λ ₃ = − (k + t); (ii) τ − 𝜃 = − t; (iii) δ = 2k + t; (iv) r = 2t(2p + 1)+k; and (v) 𝜃 = 2t(2p + 1)−(k ² + (t − 1)k). Using (ii), (iv), and (v), we can easily see that (1) is reduced to

$$ (4p+3)t^{2} - 4(2p+1)t + 2k^{2} + 2k(2t-1) = 0. $$

(11)

Case 1

(t = 0). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − k, τ − 𝜃 = 0, δ = 2k,r = k, and 𝜃 = − k ² + k, a contradiction.

Case 2

(t = 1). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − (k + 1), τ − 𝜃 = −1,δ = 2k + 1,r = 2(2p + 1)+k, and 𝜃 = 2(2p + 1)−k ². Using (11), we find that 4p + 1=2k(k + 1), a contradiction because 2∤(4p + 1).

Case 3

(t = 2). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = k and λ ₃ = − (k + 2), τ − 𝜃 = −2,δ = 2(k + 1),r = 4(2p + 1)+k, and 𝜃 = 4(2p + 1)−(k ² + k). Using (11), we find that (k + 1)(k + 2) = 0, a contradiction.

Case 4

(t = 3 and t = −1,−2). Using (11), we find that (x) 12p + 2k ² + 10k + 5=0; (y) 12p + 2k ² − 6k + 7=0; and (z) 16p + k ² − 5k + 10=0 for t = 3,t = −1, and t = −2, respectively, a contradiction.

□

Proposition 18

Let G be a connected strongly regular graph of order 4(2p + 1) and degree r, where 2p + 1 is a prime number. If m ₃ = 3(2p + 1) and m ₂ = 2p, then G belongs to the class $(\overline 5^{0})$ represented in Theorem 3.

Proof

Using (2), we obtain 4p(3|λ ₃| − λ ₂) = 3(τ − 𝜃) −3δ + r. Since 3(τ − 𝜃) −3δ = 6λ ₃, it follows that −16p ≤ 3(τ − 𝜃)−3δ + 2r ≤ 16p. Let 3|λ ₃| − λ ₂ = t where −4 ≤ t ≤ 4. Let λ ₃ = − k where k is a positive integer. Then (i) λ ₂ = 3k − t; (ii) τ − 𝜃 = 2k − t; (iii) δ = 4k − t; (iv) r = 2p t + 3k; and (v) 𝜃 = 2p t − (3k ² − (t + 3)k). Using (ii), (iv), and (v), we can easily see that (1) is reduced to

$$ t(t-4)p + 6k(k-1) = 0. $$

(12)

Case 1

(t = 0). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = 3k and λ ₃ = − k,τ − 𝜃 = 2k,δ = 4k,r = 3k, and 𝜃 = − 3k ² + 3k. Using (12), we find that k(k − 1) = 0, which yields that 𝜃 = 0. So we obtain that G is disconnected, a contradiction.

Case 2

(t = 1). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = 3k + 1 and λ ₃ = − k, τ − 𝜃 = 2k − 1,δ = 4k − 1,r = 2p + 3k, and 𝜃 = 2p − (3k ² − 4k). Using (12), we find that p = 2k(k − 1), which yields that 2p + 1=(2k − 1)², a contradiction.

Case 3

(t = 2). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = 3k − 2 and λ ₃ = − k, τ − 𝜃 = 2(k − 1),δ = 2(2k − 1),r = 4p + 3k, and 𝜃 = 4p − (3k ² − 5k). Using (12), we find that 2p = 3k(k − 1). Replacing k with k + 1, we obtain that G is the strongly regular graph of order 4(3k ² + 3k + 1) and degree r = 3(k + 1)(2k + 1) with τ = (k + 2)(3k + 1) and 𝜃 = (k + 1)(3k + 2).

Case 4

(t = 3). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = 3(k − 1) and λ ₃ = − k, τ − 𝜃 = 2k − 3,δ = 4k − 3,r = 6p + 3k, and 𝜃 = 6p − (3k ² − 6k). Using (12), we find that p = k(k − 1), which yields that 2p + 1=(2k − 1)², a contradiction.

Case 5

(t = 4). Using (i), (ii), (iii), (iv), and (v), we find that λ ₂ = 3k − 4 and λ ₃ = − k, τ − 𝜃 = 2(k − 2),δ = 4(k − 1),r = 8p + 3k, and 𝜃 = 6p − (3k ² − 7k). Using (12), we find that k(k − 1) = 0, a contradiction.

Case 6

(t ≤ −1). In this case, we find that |t|(|t|+4)p + 6k(k − 1) = 0, a contradiction (see (12)).

□

Theorem 3

Let G be a connected strongly regular graph of order 4(2p+1) and degree r, where 2p+1 is a prime number. Then G is one of the following strongly regular graphs:

• (1⁰) G is the complete bipartite graph K _{4p + 2, 4p + 2} of order n = 4(2p + 1) and degree r = 4p + 2 with τ = 0 and = 4p + 2, where $p\in \mathbb N$ and 2p + 1 is a prime number. Its eigenvalues are λ ₂ = 0 and λ ₃ = −(4p + 2) with m ₂ = 8p + 2 and m ₃ = 1;

• (2⁰) G is the strongly regular graph $\overline {4K_{2p+1}}$ of order n = 4(2p + 1) and degree r = 6p + 3 with τ = 4p + 2 and𝜃= 6p + 3, where $p\in \mathbb N$ and 2p + 1 is a prime number. Its eigenvalues are λ ₂ = 0 and λ ₃ = −(2p + 1) with m ₂ = 8p and m ₃ = 3;

• (3⁰) G is the strongly regular graph $\overline {(2p+1)K_{4}}$ of order n = 4(2p + 1) and degree r = 8p with τ = 8p − 4 and = 8p, where $p\in \mathbb N$ and 2p + 1 is a prime number. Its eigenvalues are λ ₂ = 0 and λ ₃ = −4 with m ₂ = 3(2p + 1) and m ₃ = 2p;

• (4⁰) G is the cocktail-party graph $\overline {(4p+2)K_{2}}$ of order n = 4(2p + 1) and degree r = 8p + 2 with τ = 8p and = 8p + 2, where $p\in \mathbb N$ and 2p + 1 is a prime number. Its eigenvalues are λ ₂ = 0 and λ ₃ = −2 with m ₂ = 2(2p + 1) and m ₃ = 4p + 1;

• (5⁰) G is the strongly regular graph of order n = 4(3k ² + 3k + 1) and degree r = 3k(2k + 1) with τ = 3k ² − k − 2 and = k(3k + 1), where $k\in \mathbb N$ and 3k ² + 3k + 1 is a prime number. Its eigenvalues are λ ₂ = k and λ ₃ = −(3k + 2) with m ₂ = 3(3k ² + 3k + 1) and m ₃ = 3k(k + 1);

• $(\overline 5^{0})$  G is the strongly regular graph of order n = 4(3k ² + 3k + 1) and degree r = 3(k + 1)(2k + 1) with τ = (k + 2)(3k + 1) and = (k + 1)(3k + 2), where $k\in \mathbb N$ and 3k ² + 3k + 1 is a prime number. Its eigenvalues are λ ₂ = 3k + 1 and λ ₃ = −(k + 1) with m ₂ = 3k(k + 1) and m ₃ = 3(3k ² + 3k + 1);

• (6⁰) G is the strongly regular graph of order n = 4(3k ² + 3k + 1) and degree r = (2k + 1)(3k + 1) with τ = 3k(k + 1) and𝜃= k(3k + 1), where $k\in \mathbb N$ and 3k ² + 3k + 1 is a prime number. Its eigenvalues are λ ₂ = 3k + 1 and λ ₃ = −(k + 1) with m ₂ = 3k ² + 3k + 1 and m ₃ = (3k + 1)(3k + 2);

• $(\overline 6^{0})$  G is the strongly regular graph of order n = 4(3k ² + 3k + 1) and degree r = (2k + 1)(3k + 2) with τ = 3k(k + 1) and = (k + 1)(3k + 2), where $k\in \mathbb N$ and 3k ² + 3k + 1 is a prime number. Its eigenvalues are λ ₂ = k and λ ₃ = −(3k + 2) with m ₂ = (3k + 1)(3k + 2) and m ₃ = 3k ² + 3k + 1;

• (7⁰) G is the strongly regular graph of order n = 4(36k ² − 20k + 3) and degree r = (4k − 1)(9k − 2) with τ = 9k ² − 8k + 1 and = k(9k − 2), where $k\in \mathbb N$ and 36k ² − 20k + 3 is a prime number. Its eigenvalues are λ ₂ = 3k − 1 and λ ₃ = −(9k − 2) with m ₂ = 4(3k − 1)(9k − 2) and m ₃ = 36k ² − 20k + 3;

• $(\overline 7^{0})$  G is the strongly regular graph of order n = 4(36k ² − 20k + 3) and degree r = 9(3k − 1)(4k − 1) with τ = 9(3k − 1)² + 3(2k − 1) and = 9(3k − 1)², where $k\in \mathbb N$ and 36k ² − 20k + 3 is a prime number. Its eigenvalues are λ ₂ = 3(3k−1) and λ ₃ = −3k with m ₂ = 36k ² − 20k + 3 and m ₃ = 4(3k − 1)(9k − 2);

• (8⁰) G is the strongly regular graph of order n = 4(36k ² + 20k + 3) and degree r = (4k + 1)(9k + 2) with τ = 9k ² + 8k + 1 and𝜃= k(9k + 2), where $k\in \mathbb N$ and 36k ² + 20k + 3 is a prime number. Its eigenvalues are λ ₂ = 9k + 2 and λ ₃ = −(3k + 1) with m ₂ = 36k ² + 20k + 3 and m ₃ = 4(3k + 1)(9k + 2);

• $(\overline 8^{0})$  G is the strongly regular graph of order n = 4(36k ² + 20k + 3) and degree r = 9(3k + 1)(4k + 1) with τ = 9(3k + 1)² − 3(2k + 1) and𝜃= 9(3k + 1)², where $k\in \mathbb N$ and 36k ² + 20k + 3 is a prime number. Its eigenvalues are λ ₂ = 3k and λ ₃ = −3(3k + 1) with m ₂ = 4(3k + 1)(9k + 2) and m ₃ = 36k ² + 20k + 3.

Proof

Using Theorem 1, we have $m_{2}m_{3}\delta ^{2} = 4(2p+1)r\,\overline r$. We shall now consider the following three cases.

Case 1

((2p + 1)∣δ ²). In this case, (2p + 1)∣δ because G is an integral graph. Since δ = λ ₂ + |λ ₃|<8p + 4 (see [3]), it follows that δ = 2p + 1 or δ = 2(2p + 1) or δ = 3(2p + 1). Using Propositions 10, 11, and 12, it turns out that G belongs to the class (1⁰) or (2⁰).

Case 2

((2p + 1)∣m ₂). Since m ₂ + m ₃ = 8p + 3, it follows that m ₂ = 2p + 1 and m ₃ = 6p + 2 or m ₂ = 2(2p + 1) and m ₃ = 4p + 1 or m ₂ = 3(2p + 1) and m ₃ = 2p. Using Propositions 13, 14, and 15, it turns out that G belongs to the class (3⁰) or (4⁰) or (5⁰) or (6⁰) or $(\overline 7^{0})$ or (8⁰).

Case 3

((2p + 1)∣m ₃). Since m ₃ + m ₂ = 8p + 3, it follows that m ₃ = 2p + 1 and m ₂ = 6p + 2 or m ₃ = 2(2p + 1) and m ₂ = 4p + 1 or m ₃ = 3(2p + 1) and m ₂ = 2p. Using Propositions 16, 17, and 18, it turns out that G belongs to the class $(\overline 5^{0})$ or $(\overline 6^{0})$ or (7⁰) or $(\overline 8^{0})$.

□