On strongly regular graphs of order n = 7(2p+1) where 2p+1 is a prime number

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:15

Thêm vào BST

Báo xấu

8
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

In recent years, determining the parameter of strongly regular graph is a important problem of the theory graph. However, when the number of vertices of a strongly regular graph (called n) is any number, determining its parameter is very difficult and nobody can solve this problem.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: On strongly regular graphs of order n = 7(2p+1) where 2p+1 is a prime number

JOURNAL OF SCIENCE OF HNUE Natural Sci., 2010, Vol. 55, No. 6, pp. 113-127 ON STRONGLY REGULAR GRAPHS OF ORDER n = 7(2p + 1) WHERE 2p + 1 IS A PRIME NUMBER Vu Dinh Hoa(∗) Hanoi National University of Education Do Minh Tuan Nam Dinh Teacher Training College (∗) E-mail: hoavd@fpt.com.vn 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 there exists non-negative integers τ and θ such that |Si ∩ Sj | = τ for any two adjacent vertices i and j, and |Si ∩ Sj | = θ for any two distinct non-adjacent vertices i and j, where Sk denotes the neighbourhood of the vertex k. We describe here the parameters n, r, τ and θ for strongly regular graphs of order 7(2p + 1), where 2p + 1 is a prime number. Keywords: Strongly regular graph, conference graph, integral graph. 1. Introduction 1.1. Some results of strongly regular graphs In recent years, determining the parameter of strongly regular graph is a im- portant problem of the theory graph. However, when the number of vertices of a strongly regular graph (called n) is any number, determining its parameter is very difficult and nobody can solve this problem. Therefore, we have some results in special cases of n: Due to Theorem 1.1 we have recently obtained the following result [2]: (i) there is no strongly regular graph of order 4p + 3 if 4p + 3 is a prime number. (ii) the only strongly regular graph of order 4p + 1 are conference graphs if 4p + 1 is a prime number. Besides [2-5], we have decribed the parameters n, r, τ and θ for strongly regular graphs of order 2(2p + 1), 3(2p + 1), 4(2p + 1), 5(2p + 1) and 6(2p + 1), where 2p + 1 is the prime number. In this article, We now proceed to establish the parameters of strongly regular graphs of order 7(2p + 1), where 2p + 1 is a prime number, as follows. In order to solve the problem. First, we have some results about relations of the parameters of strongly regular graphs: 113
Vu Dinh Hoa and Do Minh Tuan (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 m2 = m3 and (iii) If m2 6= m3 then G is an integral graph. (iv) If G is disconnected strongly regular graph of degree r then G = mKr+1 , where mH denotes the m−fold union of the graph H. (v) G is a disconnected strongly regular graph if only if θ = 0. 1.2. Definitions Definition 1.1. A regular graph is a graph where each vertex has the same number of neighbours, i.e. every vertex has the same degree or valency. A regular graph with vertices of degree k is called a k-regular graph or regular graph of degree k. Definition 1.2. A regular graph G of order n and degree r ≥ 1 (which is not the complete graph) is strongly regular if there exist non-negative integers τ and θ such that |Si ∩ Sj | = τ for any two adjacent vertices i and j, and |Si ∩ Sj | = θ for any two distinct non-adjacent vertices i and j, where Sk denotes the neighbourhood of the vertex k. Set of strongly regular graph with parameters (n, r, τ, θ) is denoted SRG(n, r, τ, θ) 1.3. Property of strongly regular graph Let G be a simple graph of order n. The spectrum of G consists of the eigenvalues λ1 ≥ λ2 ≥ · · · ≥ λn of its (0, 1) adjacent matrix A (0, 1) and denoted by σ(G). We say that a regular connected graph G is strongly regular if and only if it has exactly three distinct eigenvalues [1]. Let λ1 = r, λ2 , λ3 denote the distinct eigenvalues of G. Let m1 = 1, m2 , m3 denote the multiplicity of r, λ2 and λ3 , respectively. Theorem 1.1 (Lepovic [2]). Let G be a connected strongly regular graph of order n and degree r. Then m2 m3 δ 2 = n.r.r where δ = λ2 − λ3 and r = (n − 1) − r. Remark 1: Let r = (n − 1) − r, λ2 = −λ3 − 1 and λ3 = −λ2 − 1 denote the distinct eigenvalues of the strongly regular graph G, where G denotes the complement of G. Then τ = n − 2r − 2 + θ and θ = n − 2r + τ where τ = τ (G) and θ = θ(G). If G ∈ SRG(n, r, τ, θ) then G ∈ SRG(n, n − 1 − r, n − 2r − 2 + θ, n − 2r + τ ). Proposition 1.1 (Elzinga [1]). Let G is a connected or disconnected strongly regular graph of order n and degree r. Then r 2 − (τ − θ + 1)r − (n − 1)θ = 0 (1.1) 114
On strongly regular graphs of order n = 7(2p + 1) where 2p + 1 is a prime number Proposition 1.2 (Elzinga [1]). Let G be a connected strongly regular graph of order n and degree r. Then 2r + (τ − θ)(m2 + m3 ) + δ(m2 − m3 ) = 0, (1.2) δ = λ2 − λ3 (1.3) Remark 2: In [1], we have some formula: τ − θ = λ2 + λ3 (1.4) δ 2 = (τ − θ)2 + 4(r − θ) (1.5) In order to solve the problem when n = 7(2p+1), we use these formulas to con- truct an equation which contains parameters of strongly regular graph (Diophantine Equation). Then, we can solve this equation by tools of number theory. 2. Main result Theorem 2.1. Let G be a connected strongly regular graph of order 7(2p+1) and de- gree r, where 2p+1 is a prime number. Then G in one of 144 classes in Parameter Table (Section 4.) Lemma 2.1. Let G be a connected strongly regular graph of order 7(2p + 1) and degree r, where 2p + 1 is a prime number. If 2p + 1|δ then G belongs to the class 1 in Parameter Table (Section 4.). Lemma 2.2. Let G be a connected strongly regular graph of order 7(2p + 1) and degree r, where 2p + 1 is a prime number. If 2p + 1|m2 then G belongs to class 2 to class 72 represented in Parameter Table (Section 4.). Lemma 2.3. Let G be a connected strongly regular graph of order 7(2p + 1) and degree r, where 2p + 1 is a prime number. If 2p + 1|m2 then G belongs to class 73 to class 144 in Parameter Table (Section 4.). 3. Proof 3.1. Proof of Lemma 2.1 2p + 1|δ then δ = k.(2p + 1), where 1 ≤ k ≤ 6. Using Theorem 1.1 we have: m2 .m3 .k 2 .(2p + 1)2 = 7.(2p + 1).r.r ⇔ m2 .m3 .k 2 .(2p + 1) = 7.r.r which means that 2p + 1|r or 2p + 1|r or 2p + 1|7 +) Case 1. 2p + 1|7 then 2p + 1 = 7. n = 21 = 3.7 we have sovled this problem with n = 3(2p + 1) in [3] 115
Vu Dinh Hoa and Do Minh Tuan +) Case 2. 2p + 1|r or 2p + 1|r. Without loss of generality we may consider only the case when 2p + 1|r. Therefore r = l.(2p + 1) with 1 ≤ l ≤ 6 ⇒ r = 14p + 6 − l.(2p + 1) = (14 − 2l)p + 6 − l 7l(2p + 1).[(14 − 2l)p + 6 − l] 7l(14 − 2l)p + 7l(6 − l) ⇒ m2 .m3 = = . k 2 (2p + 1) k2 We have (m2 − 1).(m3 − 1) + 1 > 0 hence m2 m3 > m2 + m3 − 2 7l(14 − 2l)p + 7l(6 − l) ⇔ > 14p + 4 k2 7 49 ⇔ 14[(l − )2 + k 2 − ].p + 7(l − 3)2 + (4k 2 − 63) < 0 (∗) If k ≥ 4 then it 2 4 doesn’t satisfy the condition (∗). So that k = 1; 2; 3. we have m2 + m3 = 14p + 6. 1) k = 1. We have m2 .m3 = 7l(14 − 2l)p + 7l(6 − l). !2 m 2 + m 3 Let ∆2 = − m2 m3 2 a) l = 1 ⇒ δ = 2p + 1, r = 2p + 1. m2 .m3 = 84p + 35 m2 , m3 is two roots of the equation: X 2 − 2(7p + 3)X + 84p + 35 = 0. ∆2 = (7p + 3)2 − (84p + 35) = 49p2 − 42p − 26. We can easily see that ∆2 is a perfect square only for p = 3 and ∆ = 17. Otherwise, m2,3 = 7p + 3 ± ∆, so we have two cases: +) m2 = 41, m3 = 7. Using (1.2), we obtain 48(τ − θ) + 828 = 0 ⇒ τ − θ = 69 − . A contradiction because τ, θ is integers. 4 46 +) m2 = 7, m3 = 41. Using (1.2) , we obtain: 48(τ −θ)−736 = 0 ⇒ τ −θ = . 3 A contradiction because τ, θ is integers. b) l = 2 ⇒ δ = 2p + 1, r = 2(2p + 1). m2 .m3 = 140p + 56. We have ∆2 = 49p2 − 98p − 47. Because ∆ is an integer, p = 3 and ∆ = 10. Therefore δ = 7, r = 14. We have two cases: 7 +) m2 = 34, m3 = 14 ⇒ 168 + 48(τ − θ) = 0 ⇒ τ − θ = − . A contradiction. 2 7 +) m2 = 14, m3 = 34 ⇒ −112 + 48(τ − θ) = 0 ⇒ τ − θ = . A contradiction. 3 c) l = 3 ⇒ δ = 2p + 1, r = 3(2p + 1). m2 .m3 = 168p + 63. ∆2 = 49p2 − 126p − 54. 116
On strongly regular graphs of order n = 7(2p + 1) where 2p + 1 is a prime number ⇒ p = 3; 11, p = 3 ⇒ ∆ = 3, δ = 7, r = 21. 7 +) m2 = 27, m3 = 21 ⇒ 48(τ − θ) + 84 = 0 ⇒ τ − θ = − . 4 +) m2 = 21, m3 = 27 ⇒ 48(τ − θ) = 0 ⇒ τ − θ = 0. Using (8) we obtain 35 49 = 02 + 4(21 − θ) ⇒ θ = . A contradiction because θ is an integer. 4 p = 11 ⇒ δ = 23, r = 69, ∆ = 67 . Sovle m2 , m3 , we have two cases:. 161 +) m2 = 147, m3 = 13 ⇒ 48(τ − θ) + 3220 = 0 ⇒ τ − θ = − . A 8 contradiction . 92 +) m2 = 13, m3 = 147 ⇒ 160(τ −θ)−2944 = 0 ⇒ τ −θ = . A contradiction. 5 d) l = 4 ⇒ m2 .m3 = 168p + 56. δ = 2p + 1, r = 4(2p + 1). ∆2 = 49p2 − 126p − 47 ⇒ p = 3; 6 p = 3 ⇒ ∆ = 4, δ = 7, r = 28. Sovle m2 , m3 , we have two cases: 7 +) m2 = 28, m3 = 20 ⇒ 48(τ − θ) + 112 = 0 ⇒ τ − θ = − . A contradiction 3 . 63 +) m2 = 28, m3 = 20 ⇒ 48(τ − θ) = 0 ⇒ τ − θ = 0. Theo (8) ta c θ = . A 4 contradiction p = 6 ⇒ ∆ = 31, δ = 13, r = 52. Sovle m2 , m3 , we have two cases: 91 +) m2 = 76, m3 = 14 ⇒ 90(τ − θ) + 910 = 0 ⇒ τ − θ = − . A contradiction 9 39 +) m2 = 14, m3 = 76 ⇒ 90(τ − θ) − 702 = 0 ⇒ τ − θ = . A contradiction 5 e) l = 5 ⇒ δ = 2p + 1 v r = 5(2p + 1). m2 .m3 = 140p + 35 ⇒ ∆2 = 49p2 − 98p − 26. Because ∆ is an integer, p = 3. p = 3 ⇒ ∆ = 11, δ = 7, r = 35. Solve equations, we have two cases: 14 +) m2 = 35, m3 = 13 ⇒ 48(τ − θ) + 224 = 0 ⇒ τ − θ = − . A contradiction 3 7 +) m2 = 13, m3 = 35 ⇒ 48(τ − θ) − 84 = 0 ⇒ τ − θ = . A contradiction 4 117
Vu Dinh Hoa and Do Minh Tuan f) l = 6 ⇒ δ = 2p + 1, r = 6(2p + 1). m2 .m3 = 84p, ∆2 = 49p2 − 42p + 9 = (7p − 3)2 . Solve equations, we have two cases: +) m2 = 14p, m3 = 6. Then τ − θ = −2p − 1. Using (8), we obtain θ = 12p + 6 and τ = 10p + 5. τ −θ+δ τ −θ−δ λ2 = = 0, λ3 = = −2p − 1. 2 2 G ∈ SRG(14p + 7, 12p + 6, 10p + 5, 12p + 6). ⇒ G ∈ SRG(14p + 7, 2p, 2p − 1, 0). But, θ = 0 ⇒ G is disconnected ⇒ G = 7K2p+1 and G = 7K2p+1 . (7p − 9)(2p + 1) +) m2 = 6, m3 = 14p. Then τ − θ = . 7p + 3 UCLN(2p+1, 7p+3) = UCLN(2p+1, 7p+3−3(2p+1)) = UCLN(2p+1, p) = UCLN(2p + 1 − 2.p, p) = UCLN(1, p) = 1. Do 7p + 3|(7p − 9)(2p + 1) ⇒ 7p + 3|7p − 9. A contradiction, because 7p − 9 < 7p + 3. 7l(7 − l) 7l(6 − l) 2) k = 2 ⇒ δ = 2(2p + 1). And m2 .m3 = p+ . 2 4 7l(7 − l) If l is odd then p is an integer. But 7l(6 − l) is odd; therefore m2 .m3 is 2 not an interger, a contradiction. So that l is even, and l = 2; 4; 6. a) l = 2, r = 2(2p + 1), δ = 2(2p + 1). m2 .m3 = 35p + 14. ∆2 = 49p2 + 7p − 5. Because ∆2 is a perfect square, @p. b) l = 4, r = 4(2p + 1), δ = 2(2p + 1). m2 .m3 = 42p + 14, ∆2 = 49p2 − 5. We have (7p − 1)2 < ∆2 < (7p)2 . A contradiction . c) l = 6, r = 6(2p + 1), δ = 2(2p + 1), m2 .m3 = 21p, ∆2 = 49p2 + 21p + 9. Do (7p + 1)2 < ∆2 < (7p + 2)2 3) k = 3 ⇒ δ = 3(2p + 1) and 14l(7 − l) 7l(6 − l) m2 .m3 = p+ . 9 9 84p + 35 a) If l = 1 then m2 .m3 = . A contradiction because 84p + 35 ≡ 2 9 mod 3. 118
On strongly regular graphs of order n = 7(2p + 1) where 2p + 1 is a prime number 140p + 56 b) If l = 2 then m2 .m3 = ⇒ p ≡ −4 mod 9, and p = 9h − 4 v 9 m2 .m3 = 140h − 56, m2 + m3 = 126h − 50. ∆2 = 3969h2 − 3290h + 681 = (63h − 26)2 − (14h + 5) We obtain (63h − 27)2 < ∆2 < (63h − 26)2 . A contradiction 56p c) If l = 3 then m2 m3 = + 7. Therefore p = 3h and m2 .m3 = 56h + 7, 3 m2 + m3 = 42h + 6. Hence ∆2 = 441h2 + 70h + 2 = (21h + 1)2 + 28h + 1. We have (21h + 1)2 < ∆2 < (21h + 2)2 . A contradiction 168p − 56 d) If l = 4 then m2 m3 = . A contradiction because 168p − 56 ≡ 1 9 mod 3. 140p + 35 e) If l = 5 then m2 .m3 = . Hence p ≡ 2 mod 9 v p = 9h + 2 and 9 m2 .m3 = 140h + 35, m2 + m3 = 126h + 34. ∆2 = 3969h2 + 2002h + 254 = (63h + 15)2 + 112h + 29. We obtain (63h + 15)2 < ∆2 < (63h + 16)2 . A contradiction 28p f) If l = 6 then m2 .m3 = . Hence p = 3h and 3 m2 m3 = 28h, m2 + m3 = 42h + 6. ∆2 = 441h2 + 98h + 9 = (21h + 2)2 + (14h + 5). Therefore, we have (21h + 2)2 < ∆2 < (21h + 3)2 . A contradiction 3.2. Proof of Lemma 2.2 m2 = k(2p + 1) (1 ≤ k ≤ 6), m3 = n − 1 − m2 = (7 − k).2p + 6 − k. Using (1.2), we obtain : 2r + (m2 + m3 )(τ − θ) + δ.(m2 − m3 ) = 0. Using (1.3),(1.4), we have: 2r + (m2 + m3 ).(λ2 + λ3 ) + (λ2 − λ3 ).(m2 − m3 ) = 0 r + kλ2 + (6 − k)λ3 = 2p(−kλ2 + (k − 7)λ3 ). Let t = −kλ2 + (k − 7)λ3 . Hence r = (2p + 1)t + λ3 1) If k = 1 then : m2 = 2p + 1, m3 = 12p + 5, λ2 = −t + 6a, λ3 = −a, r = (2p + 1)t − a, Using (1.3), we have δ = λ2 − λ3 = −t + 7a. Using (1.4), we have τ − θ = λ2 + λ3 = −t + 5a. Otherwise, Using (1.5), we obtain: θ = (2p + 1 + a)t − 6a2 − a. 119
Vu Dinh Hoa and Do Minh Tuan Therefore, τ = (2p + a)t − 6a2 + 4a. Replace them into Equation (1.1) and transform it, we have: 2(p + 1)t2 − (14p + 7 + 14a)t + 42a2 + 7a = 0 (3.1) a) If t = 0 then 42a2 + 7a = 0 ⇒ a = 0. Hence θ = 0 and G is disconnected. A contradiction. b) If t = 1 then 12p = 5 − 7a + 42a2 thus a = 12h − 5 ⇒ p = 504h2 − 427h + 90. G ∈ SRG(7(1008h2 −854h+181), 1008h2 −866h+186, 144h2 −74h+5, 144h2 − 134h + 31) +) m2 = 1008h2 − 854h + 181, m3 = 6048h2 − 5124h + 1085 λ2 = 72h − 31, λ3 = −12h + 5. c) If t = 2 then 20p = −6−21a+42a2 . Hence, a = 20h+2 ⇒ p = 840h2 +14h+6. G ∈ SRG(7(1680h2 + 294h + 13), 3360h2 + 568h + 24, 12 + 228h + 960h2 , 4 + 128h + 960h2 ) +) m2 = 1680h2 + 294h + 13, m3 = 10080h2 + 1764h + 77 λ2 = 10 + 120h, λ3 = −20h − 2. d) If t = 3 then 24p = −3 − 35a + 42a2 . ⇒ a = 24h − 3 ⇒ p = 1008h2 − 287h + 20. G ∈ SRG(7(2016h2 −574h+41), 6048h2 −1746h+126, 45−690h+2592h2 , 63− 810h + 2592h2 ) and m2 = 2016h2 − 574h + 41, m3 = 12096h2 − 3444h + 245 λ2 = −21 + 144h, λ3 = −24h + 3. e) If t = 4 then 24p = 4 − 49a + 42a2 . ⇒ a = 24h + 4 ⇒ p = 1008h2 + 287h + 20. G ∈ SRG(7(2016h2 +574h+41), 8064h2 +2272h+160, 96+1336h+4608h2, 80+ 1216h + 4608h2 ) and m2 = 2016h2 + 574h + 41, m3 = 12096h2 + 3444h + 245 λ2 = 20 + 144h, λ3 = −24h − 4. f) If t = 5 then 20p = 15 − 63a + 42a2 . ⇒ a = 20h − 1 ⇒ p = 840h2 − 147h + 6. G ∈ SRG(7(1680h2 −294h+13), 8400h2 −1490h+66, 45−1050h+6000h2 , 55− 1150h + 6000h2 ) and m2 = 1680h2 − 294h + 13, m3 = 10080h2 − 1764h + 77 λ2 = −11 + 120h, λ3 = −20h + 1. 120
On strongly regular graphs of order n = 7(2p + 1) where 2p + 1 is a prime number g) If t = 6 then 12p = 30 − 77a + 42a2 . ⇒ a = 12h + 6 ⇒ p = 504h2 + 427h + 90. G ∈ SRG(7(1008h2 + 854h + 181), 6048h2 + 5112h + 1080, 924 + 4380h + 5184h2 , 900 + 4320h + 5184h2) and m2 = 1008h2 + 854h + 181, m3 = 6048h2 + 5124h + 1085 λ2 = 30 + 72h, λ3 = −12h − 6. 7 h) If t = 7 then 42a2 − 91a + 49 = 0 ⇔ a = 1 or a = (a contradiction) 6 If a = 1 then λ2 = −1 < 0 (a contradiction). i) If t < 0 or t > 7 then t2 − 7t > 0. Using 3.1, we have 2p(t2 − 7t) = −2t2 + (14a + 7)t − 42a2 − 7a. Thus −2t2 + (14a + 7)t − 42a2 − 7a > 0 ⇔ 2t2 − (14a + 7)t + 42a2 + 7a < 0. This inequation have roots if and only if (14a + 7)2 − 4.2(42a2 + 7a) > 0 √ √ 1 15 1 15 ⇔ −140a2 + 140a + 49 > 0 ⇔ − 7. 7 Case 2:a = 1. We have 2t2 − 21t + 49 < 0 ⇔ < t < 7. A contradiction. 2 2) We consider cases: k = 2, 3, 4, 5, 6, we have all of results in Lemma 2.2 3.3. Proof of Lemma 2.3 m3 = k(2p + 1) (1 ≤ k ≤ 6), m2 = n − 1 − m2 = (7 − k).2p + 6 − k. Using (1.2), we have : 2r + (m2 + m3 )(τ − θ) + δ.(m2 − m3 ) = 0. Using (1.3),(1.4), we have: 2r + (m2 + m3 ).(λ2 + λ3 ) + (λ2 − λ3 ).(m2 − m3 ) = 0 r + (6 − k)λ2 + kλ3 = 2p((k − 7)λ2 − kλ3 ). Let t = (k − 7)λ2 − kλ3 . Hence, r = (2p + 1)t + λ2 1) k = 1,, we have : m2 = 12p + 5, m3 = 2p + 1, λ2 = a, λ3 = −t − 6a, r = (2p + 1)t + a, Using (1.3), we have δ = λ2 − λ3 = t + 7a. Using (1.4), we have τ − θ = λ2 + λ3 = −t − 5a. Using (1.5), we have: θ = (2p + 1 + a)t − 6a2 − a. 121
Vu Dinh Hoa and Do Minh Tuan It follows τ = (2p + a)t − 6a2 + 4a. Replacing these variable in (1.1) and simplifying, we have: 2(p + 1)t2 − (14p + 7 − 14a)t + 42a2 − 7a = 0 (3.2) a) If t = 0 then 42a2 − 7a = 0 hay a = 0. Thus θ = 0 and G is disconnected. A contradiction . b) If t = 1 then 12p = 42a2 + 7a − 5. Thus a = 12h + 5 ⇒ p = 504h2 + 427h + 90. G ∈ SRG(7(1008h2 +854h+181), 1008h2 +866h+186, 74h+5+144h2, 144h2 + 134h + 31) and m2 = 6048h2 + 5124h + 1085, m3 = 1008h2 + 854h + 181 λ2 = 12h + 5, λ3 = −31 − 72h. c) If t = 2 then 20p = −6 + 21a + 42a2 . Thus a ≡ −6; −2 mod 20. +) Case 1: a = 20h − 6 ⇒ p = 840h2 − 483h + 69. G ∈ SRG(7(1680h2 − 966h + 139), 3360h2 − 1912h + 272, −612h + 96 + 960h2 , 960h2 − 512h + 68) and m2 = 10080h2 − 5796h + 833, m3 = 1680h2 − 966h + 139 λ2 = 20h − 6, λ3 = 34 − 120h. +) Case 2: a = 20h − 2 ⇒ p = 840h2 − 147h + 6. G ∈ SRG(7(1680h2−294h+13), 3360h2−568h+24, −228h+12+960h2, 960h2− 128h + 4) and m2 = 10080h2 − 1764h + 77, m3 = 1680h2 − 294h + 13 λ2 = 20h − 2, λ3 = 10 − 120h. d) If t = 3 then 24p = −3 + 35a + 42a2 . ⇒ a = 24h + 3 ⇒ p = 1008h2 + 287h + 20. G ∈ SRG(7(2016h2+574h+41), 6048h2+1746h+126, 690h+45+2592h2, 2592h2 + 810h + 63) and m2 = 12096h2 + 3444h + 245, m3 = 2016h2 + 574h + 41 λ2 = 24h + 3, λ3 = −21 − 144h. e) If t = 4 then 24p = 4 + 49a + 42a2 . ⇒ a = 24h − 4 ⇒ p = 1008h2 − 287h + 20. G ∈ SRG(7(2016h2 − 574h + 41), 8064h2 − 2272h + 160, −1336h + 96 + 4608h2 , 4608h2 − 1216h + 80) and m2 = 12096h2 − 3444h + 245, m3 = 2016h2 − 574h + 41 λ2 = 24h − 4, λ3 = 20 − 144h. f) If t = 5 then 20p = 15 + 63a + 42a2 . ⇒ a ≡ 1; 5 mod 20. 122
On strongly regular graphs of order n = 7(2p + 1) where 2p + 1 is a prime number +) Case 1: a = 20h + 1 ⇒ p = 840h2 + 147h + 6. G ∈ SRG(7(1680h2+294h+13), 8400h2+1490h+66, 1050h+45+6000h2, 6000h2+ 1150h + 55) and m2 = 10080h2 + 1764h + 77, m3 = 1680h2 + 294h + 13 λ2 = 20h + 1, λ3 = −11 − 120h. +) Case 2: a = 20h + 5 ⇒ p = 840h2 + 483h + 69. G ∈ SRG(7(1680h2 + 966h + 139), 8400h2 + 4850h + 700, 3450h + 495 + 6000h2 , 6000h2 + 3550h + 525) and m2 = 10080h2 + 5796h + 833, m3 = 1680h2 + 966h + 139 λ2 = 20h + 5, λ3 = −35 − 120h. g) If t = 6 then 12p = 30 + 77a + 42a2 . ⇒ a = 12h + 6 ⇒ p = 504h2 + 581h + 167. G ∈ SRG(7(1008h2 + 1162h + 335), 6048h2 + 6984h + 2016, 5988h + 1728 + 5184h2 , 5184h2 + 6048h + 1764) and m2 = 6048h2 + 6972h + 2009, m3 = 1008h2 + 1162h + 335 λ2 = 12h + 6, λ3 = −42 − 72h. 7 h) If t = 7 then 42a2 + 91a + 49 = 0 ⇔ a = −1 or a = (Loi) 6 If a = −1 then λ2 = −1 < 0 (V l). i) If t < 0 or t > 7 then t2 − 7t > 0. Using (3.2), we have 2p(t2 − 7t) = −2t2 + (−14a + 7)t − 42a2 + 7a. It follows −2t2 +(−14a+7)t−42a2 +7a > 0 ⇔ 2t2 −(−14a+7)t+42a2 −7a < 0. This inequation have roots if and only if (−14a + 7)2 − 4.2(42a2 − 7a) > 0 √ √ 1 15 1 15 ⇔ −140a2 − 140a + 49 > 0 ⇔ − −
Vu Dinh Hoa and Do Minh Tuan 4. Table of parameters on strongly regular graph when n = 7(2p + 1) Parameter Table n = 7(A.h2 + B.h + C) r = 7(A.h2 + B.h + C) τ = 7(A.h2 + B.h + C) θ = 7(A.h2 + B.h + C) Class A B C A B C A B C A B C 1 n = 7 (2p + 1) r = 12p + 6 τ = 10p + 5 θ = 12p + 6 2 1008 −854 181 1008 −886 186 144 −74 5 144 −134 31 3 1680 294 13 3360 568 24 960 228 12 960 128 4 4 2016 −574 41 6048 −1746 126 2592 −690 45 2592 −810 63 5 2016 574 41 8064 2272 160 4608 1336 96 4608 1216 80 6 1680 −294 13 8400 −1490 66 6000 −1050 45 6000 −1150 55 7 1008 854 181 6048 5112 1080 5184 4380 924 5184 4320 900 8 420 −350 73 420 −362 78 60 −38 5 60 −56 13 9 420 −70 3 420 −82 4 60 2 −1 60 −16 1 10 420 70 3 420 58 2 60 22 1 60 4 0 11 420 350 73 420 338 68 60 62 15 60 44 8 12 700 −294 31 1400 −608 66 400 −158 15 400 −188 22 13 700 406 59 1400 792 112 400 342 36 400 212 28 14 840 −658 129 2520 −1998 396 1080 −864 165 1080 −882 180 15 840 −238 17 2520 −738 54 1080 −306 21 1080 −342 27 16 840 −98 3 2520 −318 10 1080 −126 3 1080 −162 6 17 840 322 31 2520 942 88 1080 414 39 1080 378 33 18 840 −1022 311 3360 −4112 1258 1920 −2348 717 1920 −2384 740 19 840 −322 31 3360 −1312 128 1920 −748 72 1920 −784 80 20 840 98 3 3360 368 10 1920 212 5 1920 176 4 21 840 238 17 3360 928 64 1920 532 36 1920 496 32 22 700 −406 59 3500 −2050 300 2500 −1470 215 2500 −1500 225 23 700 294 31 3500 1450 150 2500 1030 105 2500 1000 100 24 420 −770 353 2520 −4632 2128 2160 −3978 1830 2160 −3996 1848 25 420 −490 143 2520 −2952 864 2160 −2538 744 2160 −2556 756 26 420 −350 73 2520 −2112 442 2160 −1818 381 2160 −1836 390 27 420 −70 3 2520 −432 18 2160 −378 15 2160 −396 18 28 224 −182 37 224 −194 42 32 −26 5 32 −30 7 29 3360 −2478 457 6720 −5016 936 1920 −1436 268 1920 −1456 276 30 3360 2898 625 6720 5736 1224 1920 1636 348 1920 1616 340 31 448 −126 9 1344 −402 30 576 −178 13 576 −186 15 32 448 126 9 1792 480 32 1024 264 16 1024 256 16 33 3360 −4242 1339 16800 −21270 6732 12000 −15230 4831 12000 −15250 4845 34 3360 −2898 625 16800 −14550 3150 12000 −10430 2265 12000 −10450 2275 35 224 −266 79 1344 −1608 480 1152 −1388 416 1152 −1392 420 36 126 154 47 126 145 46 18 127 45 18 124 45 37 210 126 19 420 237 42 120 412 16 120 407 18 38 210 294 103 420 573 204 120 508 200 120 503 200 39 252 182 33 756 528 105 324 840 48 324 834 51 40 252 434 187 756 1284 558 324 1164 549 324 1158 549 41 252 70 5 1008 262 34 576 964 −252 576 958 −246 42 252 322 103 1008 1270 417 576 1540 374 576 1534 377 124
On strongly regular graphs of order n = 7(2p + 1) where 2p + 1 is a prime number 43 210 126 19 1050 615 111 750 1285 −264 750 1280 −257 44 210 294 103 1050 1455 525 750 1885 370 750 1880 375 45 126 350 243 756 2091 1470 648 2400 1248 648 2397 1254 46 1680 −910 123 1680 −970 140 240 −178 31 240 −142 21 47 1680 1330 263 1680 1270 240 240 142 19 240 178 33 48 112 70 11 224 120 16 64 20 0 64 32 4 49 3360 1610 193 10080 4710 550 4320 1926 213 4320 1998 231 50 3360 3850 1103 10080 11430 3240 4320 4806 1335 4320 4878 1377 51 3360 −1610 193 13440 −6560 800 7680 −3848 480 7680 −3776 464 52 3360 2870 613 13440 11360 2400 7680 6392 1328 7680 6464 1360 53 112 154 53 560 750 250 400 518 165 400 530 175 54 1680 910 123 10080 5400 720 8640 4572 600 8640 4608 612 55 1680 2102 613 10080 12552 3640 8640 10764 3084 8640 10800 3108 56 28 14 1 28 2 0 4 −10 −1 4 0 0 57 28 42 15 28 30 8 4 −6 −5 4 4 1 58 420 −42 1 840 −144 6 240 −94 5 240 −44 2 59 420 42 1 840 24 0 240 −46 −2 240 4 0 60 420 378 85 840 696 144 240 146 18 240 196 40 61 420 462 127 840 864 222 240 194 35 240 244 62 62 56 −14 1 168 −66 6 72 −50 5 72 −30 3 63 56 14 1 168 18 0 72 −14 −3 72 6 0 64 56 −14 1 224 −80 6 128 −68 5 128 −48 4 65 56 14 1 224 32 0 128 −4 −4 128 16 0 66 420 −42 1 2100 −270 6 1500 −250 5 1500 −200 5 67 420 42 1 2100 150 0 1500 50 −5 1500 100 0 68 420 378 85 2100 1830 396 1500 1250 255 1500 1300 280 69 420 462 127 2100 2250 600 1500 1550 395 1500 1600 425 70 28 14 1 168 72 0 144 50 −6 144 60 0 71 28 42 15 168 240 78 144 194 55 144 204 66 72 n = 7 (2p + 1) r = 14p τ = 14p − 7 θ = 14p 73 1008 854 181 1008 866 186 144 74 5 144 134 31 74 1680 −966 139 3360 −1912 272 960 −612 96 960 −512 68 75 1680 −294 13 3360 −568 24 960 −228 12 960 −128 4 76 2016 574 41 6048 1746 126 2592 690 45 2592 810 4 77 2016 −754 41 8064 −2272 160 4608 −1336 96 4608 −1216 80 78 1680 294 13 8400 1490 66 6000 1050 45 6000 1150 55 79 1680 966 139 8400 4850 700 6000 3450 495 6000 3550 525 80 1008 1162 335 6048 6984 2016 5184 5988 1728 5184 6048 1764 81 420 −70 3 420 −58 2 60 −22 1 60 −4 0 82 420 70 3 420 82 4 60 −2 −1 60 16 1 83 420 350 73 420 362 78 60 38 5 60 56 13 84 420 490 143 420 502 150 60 58 13 60 76 24 85 700 −406 59 1400 −792 112 400 −242 36 400 −212 28 86 700 294 31 1400 608 66 400 158 15 400 188 22 87 840 −322 31 2520 −942 88 1080 −414 39 1080 −378 33 88 840 98 3 2520 318 10 1080 126 3 1080 162 6 89 840 238 17 2520 738 54 1080 306 21 1080 342 27 125
Vu Dinh Hoa and Do Minh Tuan 90 840 658 129 2520 1998 396 1080 846 165 1080 882 180 91 840 −238 17 3360 −928 64 1920 −532 36 1920 −496 32 92 840 −98 3 3360 −368 10 1920 −212 5 1920 −176 4 93 840 322 31 3360 1312 128 1920 748 72 1920 784 80 94 840 1022 311 3360 4112 1258 1920 2348 717 1920 2384 740 95 700 406 59 3500 2050 300 2500 1470 215 2500 1500 225 96 700 1106 437 3500 5550 2200 2500 3970 1575 2500 4000 1600 97 420 350 73 2520 2112 442 2160 1818 381 2160 1836 390 98 420 490 143 2520 2952 864 2160 2538 744 2160 2556 756 99 420 770 353 2520 4632 2128 2160 3978 1830 2160 3996 1848 100 420 910 493 2520 5472 2970 2160 4698 2553 2160 4716 2574 101 224 182 37 224 194 42 32 26 5 32 30 7 102 3360 2478 457 6720 5016 936 1920 1436 268 1920 1456 276 103 3360 3822 1087 6720 7704 2208 1920 2204 632 1920 2224 644 104 448 126 9 1344 402 30 576 178 13 576 186 15 105 448 770 331 1792 3104 1344 1024 1784 776 1024 1792 784 106 3360 2898 625 16800 14550 3150 12000 10430 2265 12000 10450 2275 107 3360 4242 1339 16800 21270 6732 12000 15230 4831 12000 15250 4845 108 224 714 569 1344 4296 3432 1152 3692 2956 1152 3696 2964 109 126 −154 47 126 −142 40 18 −16 3 18 −19 5 110 210 −294 103 420 −568 192 120 −153 48 120 −158 52 111 210 −126 19 420 −232 32 120 −57 6 120 −62 8 112 252 −182 33 756 −522 90 324 −210 33 324 −216 36 113 252 70 5 756 234 18 324 114 9 324 108 9 114 252 −322 103 1008 −1264 396 576 −706 215 576 −712 220 115 252 −70 5 1008 −256 16 576 −130 6 576 −136 8 116 210 −294 103 1050 −1450 500 750 −1020 345 750 −1025 350 117 210 −126 19 1050 −610 88 750 −420 57 750 −425 60 118 126 −350 243 756 −2088 1440 648 −1779 1218 648 −1782 1224 119 1680 −1330 263 1680 −1270 240 240 −142 19 240 −178 33 120 1680 910 123 1680 970 140 240 178 31 240 142 21 121 112 −70 11 224 −120 16 64 −20 0 64 −32 4 122 3360 −1610 193 10080 −4170 550 4320 −1926 213 4320 −1998 231 123 3360 2870 613 10080 8730 1890 4320 3834 849 4320 3762 819 124 3360 −2870 613 13440 −11360 2400 7680 −6392 1328 7680 −6464 1360 125 3360 1610 193 13440 6560 800 7680 3848 480 7680 3776 464 126 112 −154 53 560 −750 250 400 −518 165 400 −530 175 127 1680 −2030 613 10080 −12120 3640 8640 −10332 3084 8640 −10368 3108 128 1680 −910 123 10080 −5400 720 8640 −4572 600 8640 −4608 612 129 28 −14 1 28 −2 0 4 10 −1 4 0 0 130 28 14 1 28 26 6 4 14 5 4 4 1 131 420 −378 85 840 −696 144 240 −146 18 240 −196 40 132 420 −42 1 840 −24 0 240 46 −2 240 −4 0 133 420 42 1 840 144 6 240 94 5 240 44 2 134 420 378 85 840 816 198 240 286 81 240 236 58 135 56 −14 1 168 −18 0 72 14 −3 72 −6 0 136 56 14 1 168 66 6 72 50 5 72 30 3 126
On strongly regular graphs of order n = 7(2p + 1) where 2p + 1 is a prime number 137 56 −14 1 224 −32 0 128 4 −4 128 −16 0 138 56 14 1 224 80 6 128 68 5 128 48 4 139 420 −378 85 2100 −1830 396 1500 −1250 255 1500 −1300 280 140 420 −42 1 2100 −150 0 1500 −50 −5 1500 −100 0 141 420 42 1 2100 270 30 1500 −230 −75 1500 −280 −95 142 420 378 85 2100 1950 450 1500 1450 345 1500 1400 325 143 28 −14 1 168 −72 0 144 −50 −6 144 −60 0 144 28 14 1 168 96 6 144 94 5 144 84 6 5. Conclusion We decribe the parameters of strongly regular graph when n = 7(2p + 1), where 2p + 1 is prime. The Parameter Table to lookup parameters r, τ, θ for every n = 7(2p + 1). However, the problem when n is any interger and Inverse Problem with n, r, τ, θ, Contruct graph G are very difficult and open. The quetions are how many cases there are when n is any interger and how we can construct a graph in the Inverse Problem. REFERENCES [1] R.J.Elzinga, 2003. Strongly regular graphs: values of λ and µ for which there are only finitely feasible (v, k, λ, µ). Electronic Journal of Linear Algebra ISSN 1081-3810, A publication of the International Linear Algebra Society, Volume 10, pp. 232-239, October 2003. [2] M. Lepovic, 2009. Some characterizations of strongly regular graphs. J. Appl. Math. and Computing, 29, pp. 373-381. DOI 10.1007/s12190-008-0138-0 [3] M. Lepovic. On strongly regular graphs of order 3(2p + 1) and 4(2p + 1) where 2p + 1 is a prime number. Mediterranean Journal of Mathematics, submitted. [4] M. Lepovic. On strongly regular graphs of order 5(2p + 1) where 2p + 1 is a prime number. Advances and Applications in Mathematical Sciences, in press. [5] M. Lepovic, 2010. On strongly regular graphs of order 6(2p + 1) where 2p + 1 is a prime number. Vietnam Journal of Mathematics 38:2, pp. 169-187. [6] Demo. http://www.mediafire.com/?1ec2mco28cqieeg 127