Improving bounds on the order of regular graphs of girth 5

Improving bounds on the order of regular graphs of girth 5 E. Abajo a, C. Balbuena b,∗, M. Bendala a, X. Marcote b aDepartamento de Matemática Aplicada I, Universidad de Sevilla, Spain bDepartament d’Enginyeria Civil i Ambiental, Universitat Politècnica de Catalunya, E-08034 Barcelona, Spain a r t i c l e i n f o Article history: Received 14 April 2018 Accepted 8 February 2019 Available online 2 March 2019 Keywords: Small regular graphs Cage Girth Amalgam Elliptic semiplane a b s t r a c t A (k,g)-graph is a k-regular graph with girth gand a (k,g)-cage is a (k,g)-graph with the fewest possible number of vertices n(k,g). Constructing (k,g)-cages and determining the order are both very hard problems. For this reason, an intensive line of research is devoted to constructing smaller (k,g)-graphs than previously known ones, providing in this way new upper bounds to n(k,g) each time such a graph is constructed. The paper focuses on girth g=5, where cages are known only for degrees k≤7. We construct (k,5)-graphs using and extending techniques of amalgamation into the incidence graphs of elliptic semiplanes of type Lintroduced and exposed by Funk (2009). The order of these graphs provides better upper bounds on n(k,5) than those known so far, for values of ksuch that either 13 ≤k≤33 or k≥66. 1. Introduction All considered graphs are undirected and simple. For undefined terminology and notations the reader may refer to [5]. Let Gbe a graph with vertex set V(G) and edge set E(G). If the vertex set is a multiplicative (additive) group, every edge {u, v} ∈ E(G) has a Cayley color, defined as the pair (uv−1)±1(±(u−v), respectively). The girth of a graph Gis the length gof a shortest cycle. The set of vertices adjacent to a vertex v∈Vis denoted N(v), and the degree of vis the cardinality of N(v). A (k,g)-graph is a k-regular graph of girth gand a (k,g)-cage is a (k,g)-graph with the fewest possible number of vertices. Constructions of cages can be found in the complete survey [8]. The order of a (k,g)-cage is denoted by n(k,g). A lower bound n0(k,g) on the number of vertices of a (k,g)-graph, known as the Moore bound, is given by: n0(k,g)={1+k+k(k−1) +···+k(k−1)(g−3)/2if gis odd; 2(1 +(k−1) +···+(k−1)g/2−1) if gis even. In this paper we focus on the cage problem for g=5. In this case n0(k,5) =1+k2, and this bound is only attained for k=2,3,7 and, perhaps, for k=57 (cf. [11]). The only known (k,5)-graphs of minimum order for k=4,5,6 are cages (cf. [13,14,18–21]). No other (k,5)-cage has been identified so far and most of the work carried out focus on constructing a new (k,5)-graph with fewer vertices, for degrees k>7. Following the notation in [8,9], the currently best known bound on n(k,5) is given by the order rec(k,5) of this graph. The goal of this paper is to improve the bounds on n(k,5), that is, to find lower values of rec(k,5). The methods are constructive, and based on the idea of amalgam. As far as we now, we reach this goal for most of the integers kin the range 13, . . . , 33, for k∈ {66,67,68}, and for every k≥74. ∗Corresponding author. E-mail addresses: [email protected] (E. Abajo), [email protected] (C. Balbuena), [email protected] (M. Bendala), [email protected] (X. Marcote). https://doi.org/10.1016/j.disc.2019.02.007 0012-365X/ 2901 Table 1 Upper bounds on the order of a (k,5)-graph. kUpper bound Due to Reference New upper bound 8 80 Royle [15] 9 96 Jørgensen [12] 10 124 Exoo [7] 11 154 Exoo [7] 12 203 Exoo [7] 13 230 Exoo [7]226 14 284 Abreu et al. [2]280 15 310 Abreu et al. [2] 16 336 Jørgensen [12] 17 436 Abajo et al. [1] 18 468 Abajo et al. [1] 19 500 Abajo et al. [1] 20 564 Abajo et al. [1] 21 666 Abajo et al. [1]658 22 704 Abajo et al. [1] 23 880 Funk [9]874 24 924 Funk [9]920 25 968 Funk [9]960 26 1012 Funk [9]1010 27 1056 Funk [9]1054 28 1200 Funk [9]1192 29 1248 Funk [9]1240 30 1404 Funk [9]1392 31 1456 Funk [9]1444 32 1624 Abajo et al. [1]1608 33 1680 Abajo et al. [1]1664 In Section 2we consider the incidence graph Lqof the elliptic semiplane of type L, and define a new amalgamation technique inspired by papers from Jørgensen [12], Funk [9] and Abreu et al. [2]. This technique requires both regular and bi-regular graphs to increase the degree of the resulting graph while removing vertices in flexible ways. We also recall a class of graphs introduced in [1] that will play a key role in our constructions. In Section 3we work with prime powers from q=11 to q=29. By using the new technique we construct (k,5)-graphs, for k∈ {13,14,21,23, . . . , 33}, that provide new bounds on n(k,5). Table 1 shows the values of rec(k,5) for 8 ≤k≤33 and highlights our contributions. In the rest of the paper we restrict ourselves to amalgams of rq-regular graphs into Lq. This has been done in [1] (cf. [1], Table 2 and Theorems 1.1, 1.2) for rq=5,6; and the achieved values of rec(k,5) for 34 ≤k≤65 and 69 ≤k≤73 remain untouched. In Section 4, (cf. Theorem 4.1 and Corollary 4.1), we deal with q=61 and prime powers q≥71. For each qwe find the best possible amalgam with rq-regular graphs to prove that n(q+rq,5) ≤2(q2−1) for 7 ≤rq≤12. This way, we improve the value rec(k,5) for k∈ {66,67,68}and from k=74 up to k=479 +12 =491. This process, which first fixes rqand then determines the related prime powers q, could continue indefinitely. Now we search for an explicit expression of rqas an increasing function of q, similar to Jørgensen’s bound (cf. [12], Corollary 19): n(q+⌊√q−1 4⌋,5)≤2(q2−1) for an odd prime power q. In Section 5(cf. Theorems 5.1–5.3) we improve this result and obtain better values of rec(k,5) for k>491. The proof of these theorems is based on the finite, relative and direct product difference sets provided by Singer [17], Bose [6] and Ganley [10], respectively. 2. Constructions Using position matrices, inspired by the ones introduced by Abreu et al. in [3], the adjacency matrix of a projective plane was directly obtained in [4]. Furthermore, using also the position matrices of a family of Latin Squares, the adjacency matrix of the following bipartite graph Lq=(L,P) was also obtained in Theorem 4.4. of [4]. Definition 2.1 ([4]).Let q≥2 be a prime power and Fqa Galois field. Denote F∗ q=Fq\ {0}. Consider the sets L= (Fq×F∗ q)∪({∞}×F∗ q) and P=(Fq×F∗ q)∪({∞}×F∗ q) and denote by ℓ[a,i],p(x,j), the elements of Land P, respectively. The bipartite graph Lq=(L,P) is defined as follows: For i∈F∗ q:N(ℓ[a,i])={{p(a+ij,j):j∈F∗ q}∪{p(∞,i)}if a∈Fq; {p(x,i):x∈Fq}if a= ∞. 2902 This graph Lqis in fact the incidence graph of an elliptic semiplane of type L. It is obtained by removing from the projective plane a line together with all its points, and another point not belonging to that line together with all the lines incident to it. Notice that the graph Lqinherits the duality principle from the projective plane: any valid sentence in Lqstill holds true when lines ℓ[a,i]and points p(x,j) are interchanged. In particular, the following properties of the graph Lqhave been proved in [4] and they play a fundamental role throughout the paper. Proposition 2.1 ([4]).Let Lqbe the bipartite graph given in Definition 2.1 for a prime power q ≥2. Denote La= {ℓ[a,i] : i∈F∗ q} and Px= {p(x,j):j∈F∗ q}, for a,x∈Fq∪{∞}. The graph Lqhas the following properties: (i) it is a q-regular graph of girth 6 with order 2(q2−1); (ii) its vertex set admits a partition L∪P, where L=⋃a∈Fq∪{∞} Laand P=⋃x∈Fq∪{∞} Px; (iii) it has diameter 4and any two distinct vertices either in Laor in Pxare at distance 4; (iv) each block Pxis connected to each block Laby a perfect matching for a,x∈Fq∪{∞}when x = a; this matching is obtained from the adjacency rule according to Definition 2.1. Property (iii) in Proposition 2.1 suggests the idea of adding new edges between vertices in the sets Laand Pxof the graph Lq in order to increase its regularity, as long as the girth of the resulting graph is at least 5. The Cayley colors (uv−1)±1of the edges {u, v}of a graph with vertex set F∗ qplay a central role [1,2,9,12]. Funk introduces the following amalgamation technique: Definition 2.2 ([9]).Given a prime power q≥3 and graphs GL,GPwith vertex set F∗ q, the amalgamation of these graphs into Lqis the graph Lq(GL,GP) obtained by adding to the graph Lqthe sets of edges {{ℓ[a,i], ℓ[a,i′]} : {i,i′} ∈ E(GL)}and {{p(x,j),p(x,j′)} : {j,j′} ∈ E(GP)}, with a,x∈Fq∪{∞}. Definition 2.3 ([9]).Given a prime power q≥3 and an integer r>0, the pair of r-regular graphs GL,GPwith vertex set F∗ q and girth g≥5 is said suitable for amalgamation into Lq, or simple suitable, if they have disjoint sets of Cayley colors in F∗ q. Jørgensen (cf. [12], Theorem 3) defines an equivalent construction and achieves the same result with a different terminology. Theorem 2.1 ([9,12]).Given a prime power q ≥3and a pair of r-regular graphs GL, GPsuitable for amalgamation into Lq, the graph Lq(GL,GP)is (q+r)-regular, has girth at least five and order 2(q2−1). Next, we provide a refinement of this technique that exploits the particularities of the perfect matchings between L∞and Px(x= ∞), and between P∞and La(a= ∞), that lead us to use specific graphs HL,HPin addition to the pair GL,GP. While in [9,12]V(GL)=V(GP)=F∗ q, in the new technique V(GL),V(GP),V(HL),V(HP)⊆F∗ q. This removal of vertices is the key to reduce the value rec(k,5). Definition 2.4. Given a prime power q≥3 and graphs GL,GP,HL,HPsuch that V(GL), V(GP), V(HL), V(HP)⊆F∗ q, the amalgamation of these graphs into Lqis the graph denoted Lq(GL,GP,HL,HP) with vertex set VL∪VPand edge set EL∪EP∪Eq, where VL=⋃a∈Fq{ℓ[a,i] : i∈V(GL)} ∪ {ℓ[∞,i] : i∈V(HL)},VP=⋃x∈Fq{p(x,j):j∈V(GP)} ∪ {p(∞,j):j∈V(HP)}, and EL=(⋃a∈Fq{{ℓ[a,i], ℓ[a,i′]} : {i,i′} ∈ E(GL)}) ∪{{ℓ[∞,i], ℓ[∞,i′]} : {i,i′} ∈ E(HL)},EP=(⋃x∈Fq{{p(x,j),p(x,j′)} : {j,j′} ∈ E(GP)})∪{{p(∞,j),p(∞,j′)} : {j,j′} ∈ E(HP)},Eq=E(Lq[VL∪VP]), where Lq[VL∪VP]denotes the subgraph of Lq induced by VL∪VP. We determine conditions on the graphs GL,GP,HL,HPto ensure that the amalgam graph Lq(GL,GP,HL,HP) is (q+r)-regular with girth at least five. Definition 2.5. Let q≥3 be a prime power, r≥0 be an integer and two partitions F∗ q=RL∪TL∪WL=RP∪TP∪WP. The ordered set of graphs (GL,GP,HL,HP) is r-suitable for amalgamation into Lq, or simply r-suitable, if it satisfies the following properties: (i)V(GL)=F∗ q\WL=RL∪TL, where the vertices in RLand TLhave degree r+|WP|and r+|WP|+1, respectively. V(GP)=F∗ q\WP=RP∪TP, where the vertices in RPand TPhave degree r+|WL|and r+|WL|+1, respectively. (ii) HLand HPare r-regular graphs with V(HL)=F∗ q\(WP∪TP)=RPand V(HP)=F∗ q\(WL∪TL)=RL. (iii) The graphs GL,GP,HLand HPhave girth at least 5. (iv)E(HL)∩E(GP)= ∅,E(HP)∩E(GL)= ∅and GL,GPhave disjoint sets of Cayley colors in F∗ q. In Fig. 1 we illustrate the partitions of F∗ qand the vertex sets of the graphs GL,GP,HL,HP. The eliminated sets are shown in dashed lines. We are interested in the properties of the amalgam graph Lq(GL,GP,HL,HP). Suitability guarantees that it is regular and free from triangles and quadrilaterals. 2903 Fig. 1. V(GL)=RL∪TL,V(GP)=RP∪TP,V(HL)=RP,V(HP)=RL. Theorem 2.2. Let q ≥3be a prime power, r ≥0be an integer, and (GL,GP,HL,HP)be an ordered set of r-suitable graphs. The graph Lq(GL,GP,HL,HP)is (q+r)-regular, has girth at least 5and order 2(q2−1) −(q+1)(|WL|+|WP|)−(|TL|+|TP|). Proof. Denote G=Lq(GL,GP,HL,HP) and G∗=Lq[VL∪VP]. Let us see that Gis (q+r)-regular by computing the degrees of the vertices of VL, (the ones of VPshould be treated in the same way). In G∗every vertex of ⋃a∈Fq{ℓ[a,i] : i∈V(GL)}has degree q−1−|WP|or q−|WP|, depending on whether i∈TLor not, because NG∗(ℓ[a,i])={{p(a+ij,j):j∈F∗ q\WP}if i∈TL; {p(a+ij,j):j∈F∗ q\WP}∪p(∞,i) if i/∈TL, and every vertex in {ℓ[∞,i] : i∈V(HL)}remains with degree q, due to NG∗(ℓ[∞,i])= {p(x,i):x∈Fq}. From the definition of GLand HL, the vertices of the set VLhave degree q+rin Gafter amalgamation. Let us check that Ghas girth at least five. Denote by Ca shortest cycle of Gand suppose, by contradiction, that |C| ≤ 4. The graph G∗has girth at least 6 and the graphs GL,GP,HL,HPhave girth at least 5, then the cycle Cmust have at least an edge contained in E(G)\E(G∗). By Proposition 2.1(iv), a triangle cannot exist in G, and Cmust be a cycle of length 4. Suppose that {ℓ[a,i], ℓ[a,i′]} is an edge of C, for a∈Fq,i,i′∈V(GL) and {i,i′} ∈ E(GL). Let p(x,j)∈V(C) be a neighbor of ℓ[a,i]and p(x,j′)∈V(C) be a neighbor of ℓ[a,i′], for x∈Fqand j,j′∈V(GP). From Definition 2.1, it follows that x=a+ij =a+i′j′, yielding ij =i′j′and (j′j−1)±1=(ii′−1)±1. Since by hypothesis GLand GPshare no Cayley color, it follows that {j,j′}/∈E(GP); hence, p(x,j) and p(x,j′) are not adjacent. Now assume that {ℓ[∞,i], ℓ[∞,i′]} is an edge of C, for i,i′∈V(HL). From Definition 2.1, edges {ℓ[∞,i],p(x,i)}and {ℓ[∞,i′],p(x,i′)}belong to E(G) for every x∈Fq. Since {i,i′} ∈ E(HL) and E(HL)∩E(GP)= ∅, vertices p(x,i) and p(x,i′) are not adjacent. The same argument holds if we suppose that {p(∞,j),p(∞,j′)}is an edge of Cwith j,j′∈V(HP). In any case, there is no cycle Cof length 4 in G.■ Remark 2.1. Let q≥3 be a prime power and r≥0 be an integer. According to Theorem 2.2, the existence of r-suitable graphs (GL,GP,HL,HP), for certain sets WL,WP,TL,TP⊆F∗ q, ensures that n(q+r,5) ≤2(q2−1) −(q+1)(|WL|+|WP|)−(|TL|+|TP|).(1) When WL=WP= ∅, the removal of γ=1, . . . , qsets La∪Pafrom Lq(GL,GP,HL,HP), for a= ∞, provides n(q+r−γ , 5) ≤2(q+1−γ)(q−1) −(|TL|+|TP|),(2) and if WL= ∅or WP= ∅, the deletion of a set La∪Pafor a= ∞from Lq(GL,GP,HL,HP) produces a (q+r−1,q+r)-regular graph. When TL=TP= ∅, the deletion of the set L∞∪P∞generates a graph which ensures that n(q+r−1,5) ≤2q(q−1) −q(|WL|+|WP|).(3) Remark 2.2. To simplify notation, we consider the natural isomorphism between the multiplicative group F∗ qand the additive group Zq−1, which allows us to identify ξu∈F∗ qwith u∈Zq−1, for a primitive root ξ∈F∗ q. Thus, we replace one group by the other in the following results. In particular, let us notice that the weight or Cayley color of an edge {u, v}is ±(u−v), for vertices u, v ∈Zq−1. By ω(G) we denote the set of Cayley colors of the edges of a graph Gwhose vertex set V(G)⊆Zq−1. Next we describe some graphs of girth at least 5 introduced in [1], which are very useful for constructing suitable graphs for amalgamation. 2904 E. Abajo, C. Balbuena, M. Bendala et al. / Discrete Mathematics 342 (2019) 2900–2910 Definition 2.6 ([1]).Let N≥5 be an integer, and let k1,...,kmbe a sequence of different odd elements from Z2N. (i) We denote by S2N(k1,...,km) the graph with vertex set Z2Nand edge set {{2v, 2v+kj} : 0≤v≤N−1,1≤j≤m} where the sum is performed modulo 2N. (ii) Let 0 <P,Q<Nbe two different even elements from Z2N. We denote by S2N(P,Q;k1,...,km) the graph obtained by adding to S2N(k1,...,km) the new edges {2v, 2v+P}and {2v+1,2v+1+Q}for 0 ≤v≤N−1, where the sum is performed modulo 2N. In the context of this paper, we recall some properties of these graphs Lemma 2.1 ([1]).Let N ≥5be an integer, and let k1,...,kmbe a sequence of different odd elements from Z2N. The following statements hold: (i) The graph S2N(k1,...,km)is m-regular, bipartite and has at most m Cayley colors in Z2N. Moreover, the girth of S2N(k1,...,km)is at least 6iff all the numbers ki−kjare different in Z2N, for i = j and 1≤i,j≤m. (ii) Let 0<P,Q<N be two different even elements from Z2N. The graph S2N(P,Q;k1,...,km)is (m+2)-regular and has at most m +2Cayley colors. Moreover, the girth of S2N(P,Q;k1,...,km)is at least 5 iff the following conditions hold in Z2N: (a) The numbers 3P,4P,3Q,4Q are different from 0. (b) All the numbers ki−kjare different for i = j and 1≤i,j≤m. (c) ki−kj= a−a′for every pair a,a′∈ {0,±P,±Q}. Lemma 2.2 ([1]).Let k1,...,kmbe a sequence of different odd integers such that all the numbers ki−kjare different in Z, for i= j and 1≤i,j≤m;and let P,Q be two positive even integers such that ki−kj= a−a′for every pair a,a′∈ {0,±P,±Q}. The following statements hold: (i) For every integer N >max{|ki|,ki−kj}, the graph S2N(k1,...,km)is m-regular, bipartite with girth at least 6and has at most m Cayley colors in Z2N. (ii) For every integer N >max{|ki|,ki−kj,a−a′}where a,a′∈ {0,±P,±Q}, the graph S2N(P,Q;k1,...,km)is (m+2)- regular, with girth at least 5and has at most m +2Cayley colors. The graphs described in Definition 2.6 are used in the rest of this paper. They will be given either by explicit constructions, or by using their relationship with finite difference sets. 3. Results for small values, 11 ≤q≤29 We provide suitable graphs (GL,GP,HL,HP) with V(GL),V(GP),V(HL),V(HP)⊆Zq−1to construct Lq(GL,GP,HL,HP) and improve rec(k,5) for k∈ {13,14,21,23,25,27,29,31,33}. Applying Remark 2.1 we also obtain new values of rec(k,5) for k∈ {24,26,28,30,32}. Theorem 3.1. The upper bounds on n(k,5) listed in the last column of Table 1for k ∈ {13,14,21,23,24,...,33}provide better values of rec(k,5). Proof. For q∈ {11,13,19,23,25,27,29}, let us consider the graph Lqgiven in Definition 2.1. Next we provide graphs (GL,GP,HL,HP), r-suitable for amalgamation into Lqwith r=k−q.Theorem 2.2 guarantees that the graph Lq(GL,GP,HL,HP) is k-regular and has girth at least 5. ▶q=11 →k=13: Consider q=11, r=2, WL=WP= ∅,TL=Z10 and TP= {0,4,5,9}. Let GLbe a Petersen graph with V(GL)=Z10, two disjoint pentagons (0,2,4,6,8,0), (1,5,9,3,7,1) and edges {0,1},{2,3},{4,5},{6,7},{8,9}joining them. Hence, the set of Cayley colors of GL(in Z10) is ω(GL)= ±{1,2,4}. Let GPbe with V(GP)=Z10 formed by S10(3,−3) and the chords {0,5},{4,9}. The set of Cayley colors of GP(in Z10) is ω(GP)= ±{3,5}, and clearly, ω(GL)∩ω(GP)= ∅. By Theorem 2.2, HP= ∅ and the vertices of HLare the vertices of degree 2 in GP, that is, V(HL)= {1,2,3,6,7,8}. Let HLbe the 6-cycle (1,2,3,8,7,6,1) which satisfies the condition E(HL)∩E(GP)= ∅. Since (GL,GP,HL,HP) is an ordered set of r-suitable graphs, the amalgam L11(GL,GP,HL,∅) is 13-regular, has girth 5 and 2(112−1) −10 −4=226 vertices. It states rec(13,5) =226. ▶q=13 →k=14: Consider q=13, WL= {2,7},WP= {7,11},TL=TP= ∅ and r=1. Let GLbe a Petersen graph formed by the disjoint pentagons (1,6,11,4,9,1), (0,5,10,3,8,0) and edges {1,8},{6,5},{11,3},{4,0},{9,10}joining them. The set of Cayley colors of GL(in Z12) is ω(GL)= ±{1,4,5}. Let GPbe a Petersen graph with disjoint pentagons (0,9,6,8,10,0), (2,5,3,1,4,2), and edges {0,2},{9,3},{6,4},{8,5},{10,1}joining them. The set of Cayley colors of GP(in Z12) is ω(GP)= ±{2,3,6}, so ω(GL)∩ω(GP)= ∅. By Theorem 2.2,V(HL)=Z12 \WP,V(HP)=Z12 \WLand the degree of both HLand HPmust be equal to r=1. Let HLbe formed by the edges {0,1},{2,3},{4,5},{8,9},{6,10}and let HPbe formed by the edges {0,3},{1,4},{6,9},{8,10},{5,11}. Notice that E(HP)∩E(GL)= ∅ and E(HL)∩E(GP)= ∅. Since the ordered set (GL,GP,HL,HP) is r-suitable, the graph L13(GL,GP,HL,HP) is 14-regular, has girth 5 and order 2(132−1) −56 =280. This provides rec(14,5) =280. 2905 ▶q=19 →k=21: For q=19, consider r=2, WL=WP= {6},TL= {0,2,4,5,7,8,10,13,14,15,16}and TP= {0,1,3, 4,5,8,11,12,13,16,17}. Let GLbe the (3,4)-regular graph formed by the hamiltonian cycle (0,5,12,13,2,16,3, 8,7,11,15,1,14,10,9,4,17,0) and the paths (1,0,7,2,9), (3,14,13,17), (11,10,5,16,15,4,8,12). Let GPbe the (3,4)-regular graph formed by the hamiltonian cycle (0,9,11,13,10,8,2,12,4,7,17,1,16,14,5,3,15,0) and the paths (2,17,11,14), (9,12,3,1,10), (7,5,8,0,16,4,13,15). Since ω(GL)= ±{1,4,5,7}and ω(GP)= ±{2,3,6,8,9}in Z18, we have ω(GL)∩ω(GP)= ∅. Graphs HLand HPwith V(HL)=Z18 \(WP∪TP) and V(HP)=Z18 \(WL∪TL) are formed by the cycles (2,7,14,15,10,9,2) and (1,3,9,11,17,12,1), respectively. Notice that E(HL)∩E(GP)=E(HP)∩E(GL)= ∅. Since all the requirements of suitability are satisfied, the graph L17(GL,GP,HL,HP) has degree 21 and girth 5. Hence rec(21,5) =2(192−1) −40 −22 =658. ▶q=23 →k=23: Consider q=23, r=0, WL= {5,10,20},WP= {1,10,17},TL=Z22 \WLand TP=Z22 \WP. Since GLand GP must have degree 4 and girth 5, both must be isomorphic to the unique (4,5)-cage [14,16]. Consider the graph GLwith vertex set V(GL)=TLformed by the two hamiltonian cycles (0,18,4,11,7,3,8,9,13,12,19,15,14,21,16,1,6,2,17,0), (0,7,12,16,17,9,4,21,3,2,19,18,1,8,15,11,6,13,14,0) and the graph GPwith V(GP)=TPformed by the two cycles (0,16,13,2,12,21,5,7,4,6,3,14,20,11,8,18,15,9,19,0), (0,12,6,8,19,7,13,11,21,9,3,16,18,5,14,2,15, 4,20,0). According to Definition 2.5 (ii), V(HL)=V(HP)= ∅. Since ω(GL)= ±{1,4,5,7,8}and ω(GP)= ±{2,3,6,9,10,11} in Z22, the suitability condition ω(GL)∩ω(GP)= ∅is satisfied and the graph L23(GL,GP,∅,∅) has degree 23 and girth 5 with 2(232−1) −24 ·6−38 =874 vertices. Then, rec(23,5) =874. ▶q=23 →k=25,24: To construct a (25,5)-regular graph, consider q=23, r=2, TL=TP= ∅,WL= {2,7}and WP= {7,14}. Let GLbe the 4-regular graph formed by the cycles (4,11,6,13,12,19,4), (0,17,21,3,8,1,18,14,10,9,16,15,20,5,0), (0,4,9,1,6,5,10,3,11,15,14,13,21,20,19,18,17,16,12,8,0), and let GPbe the 4-regular graph formed by the cycles (0,9,6,4,13,16,18,12,15,17,20,11,21,19,3,1,10,8,5,2,0), (9,15,13,11,5,3,9), (0,10,21,12,2,4,1,20,18,6, 8,17,19,16,0). Since in Z22,ω(GL)= ±{1,4,5,7,8}and ω(GP)= ±{2,3,6,9,10,11}, we have ω(GL)∩ω(GP)= ∅. Let HLand HPbe the cycles (0,4,3,8,12,16,20,2,6,10,18,11,15,19,1,5,13,9,17,21,0) and (0,3,6,9,12,15,18,5,21, 1,4,10,13,16,19,8,11,14,17,20,0), respectively. Clearly, V(HL)=Z22 \WP,V(HP)=Z22 \WL. Also, E(HL)∩E(GP)= ∅ and E(HP)∩E(GL)= ∅. Since the suitability conditions are satisfied, the graph L23(GL,GP,HL,HP) has girth 5, is 25-regular and has 2(232−1) −4·24 =960 vertices which gives the new value rec(25,5) =960. Moreover, from Remark 2.1 (3) we have the new bound rec(24,5) =920. ▶q=23 →k=27,26: To construct a (27,5)-regular graph, consider q=23, r=4, WL=WP=TL= ∅ and TP= {6,17}. Let GL=S22(4,8;1,−1), which is a 4-regular graph of girth 5 with ω(GL)= ±{1,4,8}. Let GPbe formed by the cycle S22(7,−7) together with the three paths (6,16,3,20,8,21,11,17), (6,12,18,15,2,13,4,7,5,17) and (6,0,10,19,9,14,5,17). Hence, GPis a (4,5)-regular graph of girth 5 with ω(GP)= ±{3,5,6,7,9,10,11}. Clearly ω(GL)∩ω(GP)= ∅. Let HLbe the graph with V(HL)=Z22 \TPformed by the cycles (0,9,8,4,5,11,3,2,20,16,12,13,14,10,1,21,15,7,18,19,0), (0,13,5,18,10,9,11,16,15,14,3,19,21,4,20,0), (1,2,7,8,12,1) and HP=S22(6,10;7,−7). It is easy to check that HLand HPare 4-regular graphs of girth 5 such that E(HL)∩E(GP)= ∅,E(HP)∩E(GL)= ∅. By Theorem 2.2,L23(GL,GP,HL,HP) has girth 5, is 27-regular and has 2(232−1) −2=1054 vertices. This provides rec(27,5) =1054. Remark 2.1 (2) states rec(26,5) =1010. ▶q=25 →k=29,28: For q=25, consider r=4, WL=WP= ∅and TL=TP= {7,11,19,23}. Let GLbe the graph S24(2,10;3,−3) together with the edges {7,19},{11,23}. Let GPbe formed by the cycles (2,17,18,11,10,14,20,19,2), (1,5,6,22,3,9,8,21,1), (0,4,23,16,12,13,7,15,0), (0,1,17,23,8,19,12,3,14,7,6,11,0), (2,15,9,18,13,21,10,16,5,20,4,22,2), and the edges {7,23},{11,19}. Let HLbe formed by the cycles (6,13,5,12,10,9,17,16,15,4,21,2,3,8,0), (0,16,20,13,4,10, 1,3,15,14,12,2,6,9,22,8,5,17,21,18,0), (1,18,14,22,20), and HPby the cycles (0,10,14,20,9,3,4,5,1,8,17,2, 13,21,15,0), (0,12,8,14,13,18,3,10,22,2,9,1,21,16,4,17,15,20,6,5,0) and (18,6,22,16,12). The graphs GL,GP, HL,HPhave girth 5, E(HL)∩E(GP)= ∅,E(HP)∩E(GL)= ∅ and ω(GL)∩ω(GP)= ∅ because ω(GL)= ±{2,3,10,12} and ω(GP)= ±{1,4,5,6,7,8,9,11}. Since the ordered set (GL,GP,HL,HP) is r-suitable, the graph L25(GL,GP,HL,HP) is 29-regular, has girth 5 and order 2(252−1) −8=1240, proving that rec(29,5) =1240. Moreover, Remark 2.1 (2) states rec(28,5) =1192. ▶q=27 →k=31,30: To construct a (31,5)-regular graph, consider q=27, r=4, WL=WP= ∅ and TL=TP= {5,7,9,19,21,23}. Let GLbe the (4,5)-regular graph with V(GL)=Z26 and E(GL)=E(S26(4,8,1,−1)) ∪ {{5,19},{7,21},{9,23}}, and let GPbe formed by the cycles (0, 10, 3, 16, 22, 13, 4, 11, 14, 12, 1, 17, 24, 0), (0, 2, 11, 8, 10, 5, 14, 9, 3, 23, 12, 18, 16, 25, 1, 6, 22, 20, 17, 7, 13, 19, 24, 21, 4, 15, 0), (2, 23, 20, 15, 9, 6, 21, 5, 25, 19, 8, 18, 7, 2), and the edges {5,7},{9,19},{21,23}. Since ω(GL)= ±{1,4,8,12}and ω(GP)= ±{2,3,5,6,7,9,10,11,13}in Z26, it follows that ω(GL)∩ω(GP)= ∅. Let HLbe the 4-regular graph with V(HL)=Z26 \TPand cycles (0,16,12,13,17,10,11,3,15,22,14,2,1,24,8,4,20,6,18,25,0), (0,1,13,20,14,10,24,6,16,15,17,18,2,3,4,0), (11,25,22,8,12,11), and HPbe the 4-regular graph with V(HP)= Z26 \TLwith cycles (0,11,8,25,13,18,3,10,22,2,12,17,24,16,1,20,15,6, 4,14,0), (0,10,25,6,12,3,1,14,17,8,20,2,13,24,15,0), (18,4,22,16,11,18). Since all the suitability conditions are satisfied, bounds (1) and (2) in Remark 2.1 establish rec(31,5) =1444 and rec(30,5) =1392, respectively. 2906 ▶q=29 →k=33,32: Consider q=29, r=4, TL=TP= {2,4,7,11,16,18,21,25}and WL=WP= ∅. Let GLbe the graph with E(GL)=E(S28(4,8;1,−1)) ∪ {{2,16},{4,18},{7,21},{11,25}} and let GPbe the graph formed by the hamiltonian cycle (0,22,12,2,20,9,11,6,8,24,15,17,14,21,27,10,3,16,19,25,7,5,26,23,4,1,13,18,0), the 28-length-path (1,22,9,3,5,18,8,25,10,13,11,23,2,14,19,26,24,21,0,16,6,17,7,20,27,4,15,12) and the edges {1,7},{2,18}, {4,16},{11,21},{12,25}. Since ω(GL)= ±{1,4,8,14}and ω(GP)= ±{2,3,5,6,7,9,10,11,12,13}in Z28, it follows that ω(GL)∩ω(GP)= ∅. Consider the 4-regular graph HLwith cycles (0,23,12,20,14,10,8,3,15,27,6,26,1,9,13,24,5,17, 22,19,0), (8,19,27,13,12,8), (0,1,20,5,6,10,9,17,23,15,14,22,26,3,24,0); and the isomorphic graph HPformed by the cycles (3,17,20,22,12,3), (0,10,23,26,8,1,27,9,5,14,24,6,13,19,15,0), (0,3,14,23,13,17,1,10,22,6,8, 5,19,12,27,24,15,26,20,9,0). The graphs GL,GP,HLand HPare r-suitable, and bounds (1) and (2) state rec(33,5) =1664 and rec(32,5) =1608, respectively. ■ 4. Results for greater values, 61 ≤q≤479 In the section above, new values of rec(k,5) are obtained by amalgams into Lq, for prime powers 11 ≤q≤29. In the next theorem we focus on q=61 and q≥71 and amalgamate regular graphs GL,GPwith degrees rq>6; similarly as in [9] for rq=4 and as in [1] for rq=5,6. Theorem 4.1. Let q ≥61 be an odd prime power. Then n(q+rq,5) ≤2(q2−1) where rqis the following integer: rq= ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 7if q ∈ {61,71, . . . , 89}; 8if q ∈ {101,...,109}; 9if q ∈ {97,113, . . . , 139}−{127,131}; 10 if q ∈ {127,131,149, . . . , 181}; 11 if q ∈ {191,...,223}; 12 if q ≥227 and q = 241; 13 if q =241. Proof. For each odd prime power q≥61 (except q=67) we construct a definite pair of suitable rq-regular graphs GLand GP.Theorem 2.1 proves that the amalgam Lq(GL,GP) is (q+rq)-regular with girth at least 5 and order 2(q2−1). Next, we provide these two graphs for q∈ {61,97,127,131}and q≥263. For the rest of values qthe graphs GL,GPare indicated in Table 2. ▶q=61 →k=68 : We consider the 7-regular graph GL=S60(12,24;1,−1,5,19,27). To construct another 7-regular graph GP, we add to the 5-regular bipartite graph S60(3,7,15,−29,29) the edges {{2i,2i+10} : 0≤i≤29}, and the edges of the five cycles (1 +2i,31 +2i,11 +2i,51 +2i,21 +2i,41 +2i,1+2i), for 0 ≤i≤4. Since both GLand GPhave girth 5 and ω(GL)∩ω(GP)= ∅, due to ω(GL)= ±{12,24,1,5,19,27}and ω(GP)= ±{10,20,30,3,7,15,29}, the graph L61(GL,GP) yields n(61 +7,5) ≤2(612−1) =7440. ▶q=97 →k=106 : Let GLbe the graph with V(GL)=Z96 and edges the ones in S96(1,−1,7,19,−23,−27,−37) (isomorphic to L7) together with the edges {2i,2i+16}, for 0 ≤i≤47, and the ones in the cycles (1+2i,49+2i,17+2i,81+2i,33+2i,65+2i,1+2i) , for 0 ≤i≤7. The graph GLis 9-regular, has girth 5 and set of Cayley colors ω(GL)= ±{16,32,48,1,7,19,23,27,37}. Let GPbe the isomorphic graph obtained from GLby the permutation on V(GL)=Z96 expressed as the following product of cycles: (1 29 62 37 19 90 55 77 76 46 27 18 11 8 4 2) ·(3 48 30 17 39 63 68 42 25 66 41 64 40 24 14 7 38 23 67 70 43 72 44 26 15 28 16 10 5 69 86 53 89 84 52 32 20 12 6) ·(9 83 92 56 34 21 79 58 35 82 51 88 54 33 60 36 22 13) ·(31 71 87 78 47 73 74 45 93 95 85 61 80 50) ·(49 59) ·(81 91 94 57). The set ω(GP)=Z96 \({0}∪ω(GL)), and the graph L96(GL,GP) yields n(96 +9,5) ≤2(972−1). ▶q=127 →k=137: We start with the graph S126(1,−1,5,13,29,39,−45,61) which is isomorphic to L8, and consider the graph GL= S126(18,36;1,−1,5,13,29,39,−45,61). It is 10 regular, has girth 5 and ω(GL)= ±{18,36,1,5,13,29,39,45,61}. The isomorphic graph GPis obtained from GLby the following permutation on V(GL)=Z126: (1 106 78 59 23 123 81 27 39 55 11 54 42 31 96 79 67 117 121 115 12 6 3 103 53 112 86 63 99 105 102 76 58 44 32 21 41 9 82 61 94 72 56 43 124 92 71 116 88 64 47 37 52 36 28 19 109 69 80 60 45 125 98 74 57 51 108 84 62 46 33 65 25 118 89 10 5 114 87 104 77 107 122 91 13 100 75 101 110 85 93 97 11 26 18 14 7 120 90 70 50 35 66 48 34 22 16 8 4 2) ·(15 38 29 40 30 20) ·(17 68 49 24) ·(113 119). Since ω(GP)∩ω(GL)= ∅, the graph L127(GL,GP) establishes n(127 +10,5) ≤2(1272−1). ▶q=131 →k=141 : Consider the 10-regular graph GL=S130(26,52;1,−1,7,−13,−31,−35,55,−59) and the isomorphic graph GP obtained by the following permutation on V(GL)=Z130: (1 34 24 12 6 3 110 83 79 77 76 52 40 27 35 111 99 118 87 121 126 91 95 54 41 56 42 28 21 58 43 39 117 103 123 122 89 115 102 72 50 32 23 33 18 9 38 26 20 10 5 13 73 74 51 17 116 86 64 46 30 22 11 94 68 48 31 37 36 25 14 7 119 120 88 2907 Table 2 The rq-regular graphs GLand GPare suitable for amalgamation into Lq. q rqGLGP 61 7 S60(12,24;1,−1,5,19,27) See proof of Theorem 4.1 71 7 S70(10,20;1,−1,5,13,−23) S70(2,4;3,−7,15,−21,31) 73 7 S72(16,28;1,−1,5,−9,25) S72(2,4;3,−7,15,−23,35) 79 7 S78(12,24;1,−1,5,−9,−27) S78(2,4;3,−7,15,−21,31) 81 7 S80(12,24;1,−1,5,−9,−29) S80(2,4;3,−7,15,−21,−39) 83 7 S82(12,24;1,−1,5,−9,−27) S82(2,4;3,−7,15,−21,31) 89 7 S88(12,24;1,−1,5,−9,−27) S88(2,4;3,−7,15,−21,33) 97 9 See proof of Theorem 4.1 See proof of Theorem 4.1 101 8 S100(16,32;1,−1,5,−9,−21,−39) S100(2,4;3,−7,15,−23,33,−43) 103 8 S102(16,32;1,−1,5,−9,−21,35) S102(2,4;3,−7,15,−23,−43,45) 107 8 S106(16,32;1,−1,5,−9,−21,29) S106(2,4;3,−7,15,−23,33,47) 109 8 S108(16,32;1,−1,5,−9,−21,29) S108(2,4;3,−7,15,−23,33,−43) 113 9 S112(18,36;1,−1,27,31,43,−47,51) S112(2,4;3,−15,25,−29,37,−39,53) 121 9 S120(18,36;1,−1,5,−11,−25,−33,45) S120(6,12;3,−7,−29,−37,41,55,57) 125 9 S124(18,36;1,−1,5,15,−25,−33,−45) S124(2,4;3,−7,−19,21,−39,47,−53) 127 10 S126(18,36;1,−1,5,13,29,39,−45,61) See proof of Theorem 4.1 131 10 S130(26,52;1,−1,7,−13,−31,−35,55,−59) See proof of Theorem 4.1 137 9 S136(18,36;1,−1,5,−9,21,49,61) S136(2,4;3,−7,15,−23,33,−43,65) 139 9 S138(18,36;1,−1,5,−9,21,33,−47) S138(2,4;3,−7,15,−23,35,49,−59) 149 10 S148(18,36;1,−1,7,−21,31,41,45,57) S148(2,4;3,−9,17,−25,−43,53,−63,−73) 151 10 S150(18,36;1,−1,5,15,−23,45,57,65) S150(2,4;3,−7,19,−21,37,49,−59,69) 157 10 S156(18,36;1,−1,5,13,−29,−39,−61,69) S156(2,4;3,−7,19,−21,−43,−55,63,−73) 163 10 S162(18,36;1,−1,5,−9,−25,−47,−59,75) S162(2,4;3,−7,15,−21,31,−41,−71,73) 167 10 S166(18,36;1,−1,5,−9,21,−41,49,−65) S166(2,4;3,−7,15,−23,33,−55,69,−69) 169 10 S168(18,36;1,−1,5,−9,−21,47,−59,81) S168(2,4;3,−7,15,−23,43,−53,67,−67) 173 10 S172(18,36;1,−1,5,−9,21,49,61,−77) S172(2,4;3,−7,15,−23,39,57,−67,−81) 179 10 S178(18,36;1,−1,5,−9,21,33,−61,79) S178(2,4;3,−7,15,−23,35,−59,−73,75) 181 10 S180(18,36;1,−1,5,−9,21,33,−61,79) S180(2,4;3,−7,15,−23,35,−37,59,−85) 191 11 S190(18,36;1,−1,5,15,−25,43,63,75,−81) S190(2,4;3,−7,17,−23,−41,49,−61,79,−89) 193 11 S192(18,36;1,−1,5,13,29,39,−45,61,81) S192(4,8;3,−3,17,−25,−35,43,73,−83,−85) 197 11 S196(18,36;1,−1,5,−9,−33,49,−61,79,95) S196(2,4;3,−7,15,35,−41,51,65,−67,89) 199 11 S198(18,36;1,−1,5,−9,−21,39,−51,67,83) S198(2,4;3,−7,15,−23,−43,55,69,87,−87) 211 11 S210(18,36;1,−1,5,−9,21,33,−57,85,−101) S210(2,4;3,−7,15,−23,−37,47,−71,−95,97) 223 11 S222(18,36;1,−1,5,−9,21,33,−47,91,−107) S222(2,4;3,−7,15,−23,35,49,−51,−75,97) 227 12 S226(18,36;1,−1,5,−9,33,49,−65,79,−85,101) S226(2,4;3,−7,15,35,−37,51,69,−93,95,−107) 229 12 S228(12,30;1,−1,5,−9,−45,57,73,−79,95,−107) S228(18,42;3,−3,11,31,41,43,−61,93,97,−109) 233 12 S232(36,72;1,−1,5,25,−39,47,59,75,−95,−105) S232(4,8;3,−7,−35,43,57,63,−69,87,−87,89) 239 12 S238(18,36;1,−1,−5,11,−29,33,59,−85,103,111) S238(2,4;3,−7,19,−37,51,63,−71,87,−89,−109) 241 13 S240(24,48;1,−1,−5,9,27,39,−55,61,−75,−91,107) S240(72,96;−3,15,−15,23,25,29,−37,79,−83,99,115) 243 12 S242(18,36;1,−1,−5,9,−21,43,75,−89,101,113) S242(2,4;3,−7,15,−23,33,−59,79,−91,103,−119) 251 12 S250(18,36;1,−1,5,−9,25,47,−59,87,99,115) S250(2,4;3,−7,15,−21,−39,43,63,−65,−95,−111) 257 12 S256(18,36;1,−1,5,−9,21,−43,61,87,99,−111) S256(2,4;3,−7,15,−23,33,−55,57,−69,−89,93) 263 12 S262(28,56;1,−1,−13,61,65,91,97,21,107,115) S262(20,40;3,−15,27,−47,49,55,57,−59,−63,−73) . . . . . . . . . . . . q12 Sq−1(28,56;1,−1,−13,61,65,91,97,21,107,115) Sq−1(20,40;3,−15,27,−47,49,55,57,−59,−63,−73) 65 127 129 125 128 92 67 53 55 19 106 81 78 60 44 29 112 84 63 114 85 168 4 2) ·(100 71 97 108 82 62 45 15 113 101 109 105 124 90 66 47) ·(61 59 107 104 80) ·(69 98 70 49 93 96). Since ω(GP)∩ω(GL)= ∅, the graph L131(GL,GP) establishes n(131 +10,5) ≤2(1312−1). ▶q≥263 →k=q+12 : Consider the graphs GL=Sq−1(28,56;1,−1,−13,61,65,91,97,21,107,115) and GP=Sq−1(20,40;3,−15,27,−47, 49,55,57,−59,−63,−73). The integers in their definitions verify the conditions in Lemma 2.2, so both of them are 12- regular graphs with girth 5 when q−1=2N>260, that is, when q≥263 is an odd prime power. As their Cayley colors are clearly disjoint, GLand GPform a suitable pair. ■ Let us notice that Theorem 4.1 is sharp when q∈ {61,71,73,79,97,113,121,127,131,149, 151,191,193,197,199}, because |V(GL)| = |V(GP)| = q−1<rec(rq+1,5), so rqis the maximum degree that the chosen suitable graphs GLand GPcan reach. In [1] the authors consider some prime powers 31 ≤q≤59 and q=64,67 to obtain bounds on n(k,5) for degrees 34 ≤k≤65 and 69 ≤k≤73. These values of rec(k,5) are sharp and remain untouched. Now, we consider greater values of k. 2908 Corollary 4.1. Given an integer k ∈ {66,67,68}and k ≥74, let q be the lowest odd prime power such that k ≤q+rq, where rqis given in Table 2. Then, n(k,5) ≤2(k−rq+1)(q−1). In particular, n(k,5) ≤2(k−11)(q−1) when 235 ≤k≤q+12. Proof. Let q∈ {61,71, . . . , }be an odd prime power, and let GL,GPbe the suitable pair of graphs provided in the proof of Theorem 4.1. The graph Lq(GL,GP) is (q+rq)-regular, has girth at least five and order 2(q+1)(q−1). Deleting iteratively from this graph γblocks of lines and γblocks of points (cf. Remark 2.1 (2)), we have n(q+rq−γ , 5) ≤2(q+1−γ)(q−1), or equivalently, n(k,5) ≤2(k−rq+1)(q−1) for k≤q+rq.■ In the following section we establish bounds better than the last one n(k,5) ≤2(k−11)(q−1) for large odd prime powers qand degrees k. 5. Results for q∈ {313,337,367}and large values q>479 In this section, thanks to a simple relationship between difference sets and graphs S2N(k1, . . . , km), we construct three distinct families of graphs which are suitable for amalgamation into Lq. This way, we obtain new bounds on n(k,5) for large values of k. In particular, we improve the known bound n(q+⌊√q−1 4⌋,5) ≤2(q2−1) for an odd prime power q proved by Jørgensen (cf. [12], Corollary 19) using also difference sets. We begin with a simple auxiliar lemma. Lemma 5.1. Let m,N be two positive integers and D = {d1,...,dm} ⊂ ZNsuch that all the numbers di−djwith i = j are different in ZN. Define K = {k1,...,km}where ki=2di+1∈Z2Nand consider an even non-zero δ∈Z2N. Then: (i) S2N(k1, . . . , km)and S2N(k1−δ, . . . , km−δ)are m-regular graphs with girth at least 6. (ii) V =K∩(K−δ)= ∅iff δ=ki−kjfor some 1≤i,j≤m. In this case, V = {ki−δ}. (iii) (−K)∩(K−δ)= ∅iff δ=ki+kjfor some 1≤i,j≤m. Proof. The assertion (i) follows from Lemma 2.1. Items (ii) and (iii) follow from direct calculations. First, if α∈K∩(K−δ), there is an ordered pair (ki,kj) with α=kj=ki−δand δ=ki−kjin Z2N. Since (ki,kj) is unique, we have V= {ki−δ}. In a similar way, if α∈(−K)∩(K−δ) then α= −ki=kj−δand δ=ki+kj.■ Roughly speaking, a subset D⊂Hof an group H(written in additive notation) is a finite difference set if every non-zero element of Hcan be represented by the same number λof differences d−d′with d,d′∈D. We only need the first and simplest class of difference sets, that is, λ=1 and Hcyclic, defined and studied by Singer [17] in 1938. Lemma 5.2 (cf. [17], Theorem 2).Given a prime power p, there is a subset D = {d0, . . . , dp} ⊂ Zp2+p+1such that each non-zero element h ∈Zp2+p+1is represented in a unique way as h =di−dj. We use these finite difference sets to obtain the following result: Theorem 5.1. Let p,q be prime powers such that q =2(p2+p+1) +1. Then n(q+√2q−5−1 2,5)≤2q2−q−1. Proof. Denote N=p2+p+1 and let {d0,...,dp} ⊂ ZNbe the difference set given by Lemma 5.2. Consider K= {k0, . . . , kp} ⊂ Z2N=Zq−1with ki=2di+1. Since the set B= {ki+kj:0≤i,j≤p}has only (p+2)(p+1)/2 elements, take an even non-zero δ∈Z2N\Band its unique representation δ=kiδ−kjδ. By Lemma 5.1 and the election of δ, the (p+1)-regular graph GL=Sq−1(k0, . . . , kp) and the p-regular graph GP=Sq−1(k0−δ, . . . , kiδ−1−δ, kiδ+1−δ, . . . , kp−δ) have girth al least 6 and disjoint sets of Cayley colors. In order to apply Theorem 2.2 for r=p,WL=WP= ∅,TL=Zq−1and TP= ∅, we define HL=Sq−1(k0, . . . , kp−1) and HP= ∅. Clearly, E(HL)∩E(GP)= ∅because ω(HL)∩ω(GP)= ∅. The graph Lq(GL,GP,HL,HP) has girth at least 5, order 2(q2−1) −(q−1) =2q2−q−1 and degree q+p=q+1 2(√2q−5−1). ■ Let us notice that the graph S2(p2+p+1)(k0, . . . , kp) is isomorphic to the incidence graph Ppof the projective plane. Actually, Singer proves the existence of finite difference sets as a consequence of a geometric property of the projective planes. Now we turn our attention to difference sets of a group H relative to a subgroup H1. We are only interested in the differences defined by Bose [6] in 1942. Lemma 5.3 (cf. [6], Theorem 1).Consider a prime power p ≥3, the cyclic group H =Zp2−1and the subgroup H1=(p+1) formed by the multiples of p +1. Then there exists a set D = {d1,...,dp} ⊂ H such that each element h ∈H\H1is represented as di−djin a unique way, and no difference di−djwith i = j lies in H1.