On strongly regular graphs of order n = 7(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 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.

pdf15 trang | Chia sẻ: thanhle95 | Lượt xem: 225 | Lượt tải: 0download
Bạn đang xem nội dung tài liệu On strongly regular graphs of order n = 7(2p + 1) where 2p + 1 is a prime number, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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 m2m3δ 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 r2 − (τ − θ + 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.k2.(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 ⇒ m2.m3 = 7l(2p+ 1).[(14− 2l)p+ 6− l] k2(2p+ 1) = 7l(14− 2l)p + 7l(6− l) k2 . We have (m2 − 1).(m3 − 1) + 1 > 0 hence m2m3 > m2 +m3 − 2 ⇔ 7l(14− 2l)p + 7l(6− l) k2 > 14p+ 4 ⇔ 14[(l − 7 2 )2 + k2 − 49 4 ].p + 7(l − 3)2 + (4k2 − 63) < 0 (∗) If k ≥ 4 then it 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). Let ∆2 = ( m2 +m3 2 )2 −m2m3 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 4 . A contradiction because τ, θ is integers. +)m2 = 7, m3 = 41. Using (1.2) , we obtain: 48(τ−θ)−736 = 0⇒ τ−θ = 46 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: +) m2 = 34, m3 = 14⇒ 168+ 48(τ − θ) = 0⇒ τ − θ = − 7 2 . A contradiction. +) m2 = 14, m3 = 34⇒ −112+ 48(τ − θ) = 0⇒ τ − θ = 7 3 . A contradiction. 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. +) m2 = 27, m3 = 21⇒ 48(τ − θ) + 84 = 0⇒ τ − θ = − 7 4 . +) m2 = 21, m3 = 27 ⇒ 48(τ − θ) = 0 ⇒ τ − θ = 0. Using (8) we obtain 49 = 02 + 4(21− θ)⇒ θ = 35 4 . A contradiction because θ is an integer. p = 11⇒ δ = 23, r = 69, ∆ = 67 . Sovle m2, m3, we have two cases:. +) m2 = 147, m3 = 13 ⇒ 48(τ − θ) + 3220 = 0 ⇒ τ − θ = − 161 8 . A contradiction . +)m2 = 13, m3 = 147⇒ 160(τ−θ)−2944 = 0⇒ τ−θ = 92 5 . A contradiction. 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: +) m2 = 28, m3 = 20⇒ 48(τ − θ) + 112 = 0⇒ τ − θ = − 7 3 . A contradiction . +) m2 = 28, m3 = 20⇒ 48(τ − θ) = 0⇒ τ − θ = 0. Theo (8) ta c θ = 63 4 . A contradiction p = 6⇒ ∆ = 31, δ = 13, r = 52. Sovle m2, m3, we have two cases: +) m2 = 76, m3 = 14⇒ 90(τ −θ)+910 = 0⇒ τ −θ = − 91 9 . A contradiction +) m2 = 14, m3 = 76⇒ 90(τ − θ)− 702 = 0⇒ τ − θ = 39 5 . A contradiction 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: +) m2 = 35, m3 = 13⇒ 48(τ −θ)+224 = 0⇒ τ −θ = − 14 3 . A contradiction +) m2 = 13, m3 = 35⇒ 48(τ − θ)− 84 = 0⇒ τ − θ = 7 4 . A contradiction 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 = τ − θ + δ 2 = 0, λ3 = τ − θ − δ 2 = −2p− 1. 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. +) m2 = 6, m3 = 14p. Then τ − θ = (7p− 9)(2p+ 1) 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. 2) k = 2⇒ δ = 2(2p+ 1). And m2.m3 = 7l(7− l) 2 p+ 7l(6− l) 4 . If l is odd then 7l(7− l) 2 p is an integer. But 7l(6− l) is odd; therefore m2.m3 is 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 m2.m3 = 14l(7− l) 9 p+ 7l(6− l) 9 . a) If l = 1 then m2.m3 = 84p+ 35 9 . A contradiction because 84p + 35 ≡ 2 mod 3. 118 On strongly regular graphs of order n = 7(2p + 1) where 2p+ 1 is a prime number b) If l = 2 then m2.m3 = 140p+ 56 9 ⇒ p ≡ −4 mod 9, and p = 9h − 4 v 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 c) If l = 3 then m2m3 = 56p 3 + 7. Therefore p = 3h and m2.m3 = 56h + 7, 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 d) If l = 4 then m2m3 = 168p− 56 9 . A contradiction because 168p − 56 ≡ 1 mod 3. e) If l = 5 then m2.m3 = 140p+ 35 9 . Hence p ≡ 2 mod 9 v p = 9h + 2 and 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 f) If l = 6 then m2.m3 = 28p 3 . Hence p = 3h and m2m3 = 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 = 1008h 2 − 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 = 1680h 2 + 294h+ 13, m3 = 10080h 2 + 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 = 2016h 2 − 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 = 2016h 2 + 574h+ 41, m3 = 12096h 2 + 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 = 1680h 2 − 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 = 1008h 2 + 854h+ 181, m3 = 6048h 2 + 5124h+ 1085 λ2 = 30 + 72h, λ3 = −12h− 6. h) If t = 7 then 42a2 − 91a+ 49 = 0⇔ a = 1 or a = 7 6 (a contradiction) If a = 1 then λ2 = −1 < 0 (a contradiction). i) If 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 ⇔ −140a2 + 140a+ 49 > 0⇔ 1 2 − √ 15 5 < a < 1 2 + √ 15 5 thus a = 0; 1. Case 1:a = 0. We have 2t2 − 7t < 0⇔ 0 < t < 7 2 . A contradiction with t < 0 or t > 7. Case 2:a = 1. We have 2t2 − 21t+ 49 < 0⇔ 7 2 < t < 7. A contradiction. 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 = 6048h 2 + 5124h+ 1085, m3 = 1008h 2 + 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 = 10080h 2 − 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 = 10080h 2 − 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 = 12096h 2 + 3444h+ 245, m3 = 2016h 2 + 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 = 12096h 2 − 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 = 10080h 2 + 1764h+ 77, m3 = 1680h 2 + 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 = 10080h 2 + 5796h+ 833, m3 = 1680h 2 + 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 = 6048h 2 + 6972h+ 2009, m3 = 1008h 2 + 1162h+ 335 λ2 = 12h+ 6, λ3 = −42− 72h. h) If t = 7 then 42a2 + 91a+ 49 = 0⇔ a = −1 or a = 7 6 (Loi) If a = −1 then λ2 = −1 < 0 (V l). i) If 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 ⇔ −140a2 − 140a+ 49 > 0⇔ −1 2 − √ 15 5 < a < −1 2 + √ 15 5 thus a = 0;−1. Case 1: If a = 0 then 2t2 − 7t < 0 ⇔ 0 < t < 7 2 . A contradiction with t < 0 or t > 7. Case 2: If a = −1 then 2t2 − 21t+ 49 < 0⇔ 7 2 < t < 7. A contradiction . 2) We consider cases: k = 2, 3, 4, 5, 6, we have all of results in Lemma 2.3 3.4. Proof of Theorem 2.1 Using Theorem 1.1 we have m2.m3.δ 2 = 7(2p+ 1).r.r. We shall now consider the following three cases: Case 1 (2p+ 1|m2): Since Lemma 2.2, we prove that G in class 2 to class 72. Case 2 (2p+ 1|m3): Since Lemma 2.3, we prove that G in class 73 to class 144. Case 3 (2p+ 1|δ2): Since Lemma 2.1, we prove that G in class 1. 123 Vu Dinh Hoa and Do Minh Tuan 4. Table of parameters on strongly regular graph when n = 7(2p+ 1) Parameter Table Class n = 7(A.h 2 +B.h + C) r = 7(A.h2 + B.h +C) τ = 7(A.h2 + B.h+ C) θ = 7(A.h2 + B.h +C) 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 −14
Tài liệu liên quan