Regular graphs of girth 5 from elliptic semiplanes of type C

Regular graphs of girth 5 from elliptic semiplanes of type C E. Abajo ∗, M. Bendala Departamento de Matemática Aplicada I, Universidad de Sevilla, Spain a r t i c l e i n f o Article history: Received 25 August 2020 Received in revised form 30 December 2020 Accepted 5 February 2021 Available online 23 February 2021 Keywords: Regular graph Cage Girth Amalgam Elliptic semiplane of type C a b s t r a c t A well-known technique to construct regular graphs with girth 5 is the amalgamation into the incidence graphs Cqand Lq, elliptic semiplanes of type Cand Lrespectively, where qis a prime power. The case qodd has extensively been studied by means of amalgamations into Lq.In this paper we provide new families of small regular graphs of girth 5 constructed by amalgamation into Cqusing finite fields of even order. 1. Introduction Ak-regular graph with girth gis called a (k,g)-graph. A classic problem in graph theory is the construction of (k,g)- cages, that is, (k,g)-graphs with the minimum number n(k,g) of vertices. We are interested in the case g=5, where there are only known cages for k=2, . . . , 7 [9,12–16]. For values of k≥8, upper bounds on n(k,5) are obtained by explicit construction of (k,5)-graphs. To reach this aim, a useful technique consists in injecting (or amalgamating) edges from a pair of rq-regular graphs with girth at least 5 into a large (q,6)-graph. With a prime power qand the incidence graph Lqof the elliptic semiplane of type L, the technique of amalgamation provides the bound n(q+rq,5)≤2(q2−1), [1,2,8,10,11]. Moreover, specific deletion of vertices from the graph resulting after amalgamation leads to n(k,5)≤2(q−1)(k+1−rq) for k≤q+rq. In 2005, for an odd prime power q, the first general construction was established in [10] with rq= ⌊1 4√q−1⌋. In [1,2] some better degrees rqwere obtained by distinct amalgamations, including the high value rq=1 √2√q+1+2, only admissible when q=2(p2−1) +1 is a prime power related to another prime power p>7. ∗Corresponding author. E-mail addresses: [email protected] (E. Abajo), [email protected] (M. Bendala). https://doi.org/10.1016/j.disc.2021.112343 0012-365X/ E. Abajo and M. Bendala Let us notice that no general result associated to even prime powers has been so far established. That is the goal of the paper. To do that, in Section 2, we describe the incidence graph Cq of the elliptic semiplane of type C together with the notation and technique of amalgamation. It provides the inequality n(q+rq,5)≤2q2, for a prime power q, [1–3,6,8]. Reduction operations after amalgamation give n(k,5)≤2q(k−rq) for k≤q+rq. The main results are shown in the third section, where we focus on even prime powers q=22s+1(Theorems 3.1,3.2) and q=22s(Theorem 3.3), for s≥3. We amalgamate into Cqa pair of suitable rq-regular graphs GLand GP, isomorphic to subgraphs of Cp, with p=2s. This way we establish two families of bounds with degree of amalgamation {rq=7 8√2√qif q=22s+1; rq=1 2√qif q=22s. By means of new amalgamations into GLand GP, in Section 4we present refinements of these bounds which, in Section 5, are applied to small values of even prime powers qand compared with the ones in [1,2]. 2. Notations and known results For undefined terminology we refer the reader to [5]. Given a graph Gwe denote by V(G) and E(G) the sets of vertices and edges of G, respectively. If A,B⊂V(G), let [A,B] ⊂ E(G) hold for the set of edges joining Aand B. If Sis a set and φ:V(G)→Sis a bijection, we write φ(G) for the graph with vertex set Sand edge set {φ(v)φ(v′):vv′∈E(G)}. Given a prime power γ, let Fγbe the finite field of order γ. The following graph Cγ, first introduced by Cronheim in [6], is the key structure throughout this paper. Definition 2.1. The bipartite graph Cγhas vertex set Lγ∪Pγ, where Lγ=⋃ a∈Fγ La=⋃ a∈Fγ{ℓa,b:b∈Fγ},Pγ=⋃ x∈Fγ Px=⋃ x∈Fγ{px,y:y∈Fγ} and edge set E(Cγ)=⋃ a,x∈Fγ[La,Px] = ⋃ a,x∈Fγ{ℓa,bpx,ax+b:b∈Fγ}. That is, the edge ℓa,bpx,y∈E(Cγ) iff y=ax +b. It is well known [4,6–8] that Cγis the incidence graph of the elliptic semiplane of type C, obtained from the projective plane by removing the points at the infinity together with the vertical lines. It is a γ-regular graph with order 2γ2, girth g=6 and diameter 4. Two vertices are at distance 4 if and only if both of them belong to the same set Laor Px. Our basic goal is to add as many edges as possible to the graph Cγin order to construct a new graph with greater degree and girth 5. To do that, in [8] the author introduces the following technique. Definition 2.2 ([8]).Let γbe a prime power. Given two graphs GL,GPwith vertex set Fγ, the amalgamation Cγ(GL,GP) is the graph obtained from Cγby adding to E(Cγ) the set of edges {ℓa,bℓa,b′:a∈Fγ,bb′∈E(GL)}∪{px,ypx,y′:x∈Fγ,yy′∈E(GP)}. The pair of graphs GL,GPmust satisfy a certain restriction to ensure that Cγ(GL,GP) has girth 5. Let us recall that given a graph Gwith vertex set Fγ, the Cayley color of an edge vv′∈E(G) is the pair ±(v−v′) if γis odd or the single element v−v′=v+v′if γis a power of two. The set of Cayley colors of the edges of Gis denoted by ω(G). Theorem 2.1 ([8]).If GL, GPare r-regular graphs with vertex set Fγ, girth g ≥5and with no common Cayley color, then Cγ(GL,GP)is a (γ+r)-regular graph with girth g ≥5. Then, n(γ+r,5) ≤2γ2. Moreover, deleting from Cγ(GL,GP)pairs of sets La,Pa, for a ∈Fγ, we have n(k,5) ≤2γ(k−r)for k ≤γ+r. We also need to introduce another result, which is a special case of Theorem 5 in [3]: 2 E. Abajo and M. Bendala Theorem 2.2 ([3]).If GL, GPare (r+1)- and r-regular graphs respectively, with vertex set Fγ, girth g ≥5and without any Cayley color in common, then Cγ(GL,GP)is a (γ+r+1, γ +r)-regular graph with girth g ≥5. Deleting the set P0, we have n(γ+r,5) ≤2γ2−γ=2γ(γ−1 2). Additionally, deleting pairs La,Pa, for a ∈Fγ\{0}, we have n(k,5) ≤2γ(k−(r+1 2)) for k ≤γ+r. These results lead us to extend the definition of suitability given in [8]. Definition 2.3. A pair of regular graphs GL,GPwith vertex set Fγ, girth g≥5 and disjoint sets of Cayley colors (in particular, a pair satisfying the hypothesis of either Theorem 2.1 or Theorem 2.2) is said to be suitable for amalgamation into Cγor, in this paper, simply suitable. 3. General results In this section, for an integer s≥2, we first deal with the prime power p=2s, the finite field Fpand the graph Cp. Given a fixed primitive element ηof Fpwith minimal polynomial g(X), the elements of the field Fp=Fp[η] ≈ F[X]/(g(X)) are given by the polynomial expressions a0+a1η+ ··· + as−1ηs−1, with a0, . . . , as−1∈F2, and can be uniquely represented by the integers a0+a12+···+as−12s−1in the range 0, . . . , p−1. Remark 3.1. For the sake of simplicity, we use this integer representation and write ‘‘a<p/2’’ to refer to the subgroup H= {0, . . . , p 2−1}. Similarly, ‘‘a≥p/2’’ refers to the coset p 2+H= {p 2,...,p−1}. Notice that a+x∈Hif and only if a,x∈Hor a,x∈p 2+H. We also consider the field Fqand the graph Cqfor q=p2or q=2p2. Our target is to construct a pair of graphs GLand GP, suitable for amalgamation into Cq. We develop this goal in two steps. First, we construct graphs ˜ GLand ˜ GPas certain subgraphs of Cp. Secondly, we define isomorphic graphs GLand GPwith vertex set Fq. The construction for odd powers of two q=2p2=22s+1and for even ones q=p2=22sis different. Notice that |V(Cp)| = 2p2, so we begin with q=2p2. 3.1. Case q =22s+1 Now we deal with an integer s≥2, and prime powers p=2s,q=2p2=22s+1. We have the relationship |V(Cp)| = 2p2= |Fq|. As we only need computations in the additive group F+ q, we use the isomorphism F+ q≈F+ 2⊕F+ p⊕F+ pto identify the elements of F+ qwith triplets (d, α, β) with d=0,1 and α, β ∈F+ p. Notice that the Cayley color of an edge (d1, α1, β1)(d2, α2, β2) joining two elements in F+ qis the single element (d1, α1, β1)−(d2, α2, β2)=(d1, α1, β1)+ (d2, α2, β2)=(d1+d2, α1+α2, β1+β2)∈F+ q\{0}. To construct ˜ GLand ˜ GP, regular subgraphs of Cp, we decompose the set E(Cp) into pperfect matchings between the sets Lpand Pp. Definition 3.1. Let p=2sbe a prime power and Cpbe the bipartite graph given in Definition 2.1. For m∈Fp, define the subset E(m)⊂E(Cp) by E(m)=⋃ a+x=m a,x∈Fp [La,Px]=⋃ a+x=m a,x∈Fp{ℓa,bpx,ax+b:b∈Fp} =⋃ a∈Fp [La,Pm+a]=⋃ a∈Fp{ℓa,bpm+a,a(m+a)+b:b∈Fp} Notice that E(Cp)= ∪m∈FpE(m). Some subsets of Fpare immediately suggested: Definition 3.2. For each m, δ ∈F∗ p, define the sets D(m)= {a x :a,x∈Fp,a+x=m} = {a(m+a):a∈Fp} Mb(δ)= {a+x:a,x∈Fp,ax =δ} Mg(δ)=Fp\Mb(δ) The following properties, based on the fact that Fpis a characteristic-two field, are critical. 3 E. Abajo and M. Bendala Lemma 3.1. For δ∈F∗ p, the following assertions hold: (i) |Mg(δ)| = p 2. (ii) If m ∈Mg(δ), then m = 0, and the sets D(m),δ+D(m)are disjoint. Proof. (i) If a+a′=mand aa′=δ, then a,a′is the unique (unordered) pair of roots of the equation X2−mX +δ=0, and a=a′iff m=a+a′=0. Then, given δ= 0, the p−1 elements of F∗ pare grouped into p/2−1 pairs a,a′with aa′=δand different values of m=a+a′= 0, and one element awith a2=δ,m=a+a=0. That is, |Mb(δ)| = p/2 and |Mg(δ)| = p/2. (ii) Since a0(m+a0)+a1(m+a1)=(a0+a1)(m+a0+a1), the set D(m) is a subgroup of the additive group F+ p. Then, D(m) and δ+D(m) are disjoint (actually, complementary) sets, unless δ∈D(m), which is equivalent to m∈Mb(δ)■ Attending the notation in Remark 3.1, for δ∈F∗ p, let us split the set Mb(δ) into disjoint sets Mb(δ)=Mb(δ)∩H and Mb(δ)=Mb(δ)∩(p 2+H). Analogously, denote Mg(δ)=Mg(δ)∩Hand Mg(δ)=Mg(δ)∩(p 2+H). Clearly, |Mg(δ)|+|Mb(δ)| = p/2 and |Mg(δ)|+|Mb(δ)| = p/2. We are going to select the largest possible set Mg(δ) or Mg(δ), for δ∈F∗ p. Definition 3.3. With the notation above, denote K=max δ∈F∗ p(max(|Mg(δ)|,|Mg(δ)|)). Notice that p/4≤K≤p/2. Now, we are ready to prove the first main result of this section: Theorem 3.1. For an integer s ≥2, denote p =2sand q =2p2=22s+1. Determine the value K according to Definition 3.3. The following assertions hold: (i) If K is even, there exists a pair of suitable graphs GL, GPwith vertex set Fqand degrees rL=rP=3p 4+K 2. Then, n(q+3p 4+K 2,5)≤2q2. (ii) If K is odd, there exists a pair of suitable graphs GL, GPwith vertex set Fqand degrees rL=3p 4+K+1 2, rP=rL−1. Moreover, n (q+3p 4+K−1 2,5)≤2q2−q. Proof. We construct a pair of graphs˜ GL,˜ GPas regular subgraphs of Cpwith girth g≥5, and bijections ΦL,ΦP:V(Cp)→Fq such that GL=ΦL(˜ GL) and GP=ΦP(˜ GP). The key point is to ensure that these graphs share no Cayley color in Fq. The definition of the bijection ΦLis rather simple: {ΦL(ℓa,b)=(0,a,b) ΦL(px,y)=(1,x,y) The rest of the construction depends on Kand its associated value δ. •K= |Mg(δ)| As |Mb(δ)| = p 2−K, we split this set into disjoint subsets M0 b(δ) and M1 b(δ) only attending that |M0 b(δ)| = ⌈(p 2−K)/2⌉ and |M1 b(δ)| = ⌊(p 2−K)/2⌋. Define subgraphs ˜ GLand ˜ GPwith vertex set V(Cp) and edges: E(˜ GL)=⋃ m∈ML E(m) with ML= {p 2,...,p−1}∪Mg(δ)∪M0 b(δ)=Fp\M1 b(δ) E(˜ GP)=⋃ m∈MP E(m) with MP= {p 2,...,p−1}∪Mg(δ)∪M1 b(δ)=Fp\M0 b(δ). Consider the bijection ΦP: ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ ΦP(ℓa,b)=(0,a,b) if a<p 2 ΦP(ℓa,b)=(1,a,b+δ) if a≥p 2 ΦP(px,y)=(1,x,y+δ) if x<p 2 ΦP(px,y)=(0,x,y) if x≥p 2 and define GL=ΦL(˜ GL) and GP=ΦP(˜ GP). Being isomorphic to subgraphs of Cp, graphs GLand GPhave g≥6. Their degrees are |ML|and |MP|, both equal to 3p 4+K 2if Kis even, or to 3p 4+K+1 2and 3p 4+K−1 2if Kis odd. The last step to prove the suitability of the pair GL,GPis to see that both graphs have no Cayley color in common. 4 E. Abajo and M. Bendala The computation of E(GL) and ω(GL) is straightforward E(GL)=⋃ m∈ML⋃ a∈Fp{(0,a,b)(1,m+a,a(m+a)+b):b∈Fp}, ω(GL)=⋃ m≥p 2 {(1,m,a(m+a)) :a∈Fp}∪ ⋃ m∈Mg(δ)∪M0 b(δ){(1,m,a(m+a)) :a∈Fp} To describe the set of edges of GPwe need to take into account Remark 3.1. E(GP)=⋃ m≥p 2⋃ a<p 2{(0,a,b)(0,m+a,a(m+a)+b):b∈Fp} ∪⋃ m≥p 2⋃ a≥p 2{(1,a,b+δ)(1,m+a,a(m+a)+b+δ):b∈Fp} ∪⋃ m∈Mg(δ)∪M1 b(δ)⋃ a<p 2{(0,a,b)(1,m+a,a(m+a)+b+δ):b∈Fp} ∪⋃ m∈Mg(δ)∪M1 b(δ)⋃ a≥p 2{(1,a,b+δ)(0,m+a,a(m+a)+b):b∈Fp} and its set of Cayley colors ω(GP)=⋃ m≥p 2 {(0,m,a(m+a)) :a∈Fp}∪ ⋃ m∈Mg(δ)∪M1 b(δ){(1,m,a(m+a)+δ):a∈Fp} By Lemma 3.1, when m∈Mg(δ), the sets D(m)= {a(m+a):a∈Fp}and D(m)+δ= {a(m+a)+δ:a∈Fp}are disjoint. By definition, M0 b(δ)∩M1 b(δ)= ∅. We conclude that ω(GL)∩ω(GP)= ∅. •K= |Mg(δ)| Now we write |Mb(δ)| = M0 b(δ)∪M1 b(δ) with |M0 b(δ)| = ⌈(p 2−K)/2⌉and |M1 b(δ)| = ⌊(p 2−K)/2⌋and define subgraphs ˜ GLand ˜ GPwith vertex set V(Cp) and edges: E(˜ GL)=⋃ m∈ML E(m) with ML= {0, . . . , p 2−1}∪Mg(δ)∪M0 b(δ)=Fp\M1 b(δ) E(˜ GP)=⋃ m∈MP E(m) with MP= {0, . . . , p 2−1}∪Mg(δ)∪M1 b(δ)=Fp\M0 b(δ). Consider the bijection ΦP: ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ ΦP(ℓa,b)=(0,a,b) if a<p 2 ΦP(ℓa,b)=(1,a+p 2,b+δ) if a≥p 2 ΦP(px,y)=(0,x+p 2,y) if x<p 2 ΦP(px,y)=(1,x,y+δ) if x≥p 2 (1) and the graphs GL=ΦL(˜ GL) and GP=ΦP(˜ GP). The girth and degrees of GLand GPare the same as in the previous case. The computation of the Cayley colors leads to: ω(GL)=⋃ m<p 2 {(1,m,a(m+a)) :a∈Fp} ∪ ⋃ m∈Mg(δ)∪M0 b(δ) {(1,m,a(m+a)) :a∈Fp} ω(GP)=⋃ m≥p 2 {(0,m+p 2,a(m+a)) :a∈Fp}∪ ⋃ m∈Mg(δ)∪M1 b(δ) {(1,m,a(m+a)+δ):a∈Fp} Both sets are disjoint. In both cases the graphs GLand GPsatisfy the hypothesis of Theorem 2.1, when Kis even, or Theorem 2.2, when Kis odd. The proof is complete. ■ The result in Theorem 3.1 depends on Kand it requires the computation of this value. By definition, K≥p 4. Then, if p=2s≥8, the conclusion of Theorem 3.1 holds when Kis the even number p 4. Theorem 3.2. Given s ≥3and q =22s+1, the following inequality holds: n(q+7 8√q 2,5)≤2q2. 5 E. Abajo and M. Bendala 3.2. Case q =22s Now we consider an integer s≥2, the prime powers p=2s,q=22s, the field Fp, the additive group F+ qand the isomorphism F+ q≈F+ 2⊕F+ p/2⊕F+ p. As in Section 3.1, we are looking for suitable amalgamations into Cq, but this time |V(Cp)| = 2p2while |Fq| = p2. Define ˜ GLand ˜ GPas the subgraphs of Cpinduced by the disjoint sets of vertices (∪a<p/2La)∪(∪x<p/2Px) and (∪a≥p/2La)∪ (∪x≥p/2Px), respectively. Clearly, |V(˜ GL)| = |V(˜ GP)| = p2=q. Also, ˜ GLand ˜ GPare p/2-regular graphs because E(˜ GL)=⋃ a<p/2⋃ x<p/2[La,Px],E(˜ GP)=⋃ a≥p/2⋃ x≥p/2[La,Px]. Writing m=a+xand taking into account Remark 3.1, we have E(˜ GL)=⋃ m<p/2⋃ a<p/2[La,Pm+a],E(˜ GP)=⋃ m<p/2⋃ a≥p/2[La,Pm+a] With these constructions, we are ready to prove the following result: Theorem 3.3. For an integer s ≥2and prime powers p =2s, q =22s, there is a pair of graphs GL, GPof degrees rL=rP=p 2 suitable for amalgamation into Cq. Then, n(q+1 2√q,5) ≤2q2. Proof. Consider the bijections ΦL:V(˜ GL)→Fqdefined as {ΦL(ℓa,b)=(0,a,b) ΦL(px,y)=(1,x,y), and ΦP:V(˜ GP)→Fqsuch that {ΦP(ℓa,b)=(0,a+p 2,b) ΦP(px,y)=(1,x+p 2,y). Define the graphs GL=ΦL(˜ GL) and GP=ΦP(˜ GP). The computation of their Cayley colors is straightforward: E(GL)=⋃ m<p/2⋃ a<p/2{(0,a,b)(1,m+a,a(m+a)+b):b∈Fp} ω(GL)=⋃ m<p/2{(1,m,a(m+a)) :a<p 2} E(GP)=⋃ m<p/2⋃ a≥p/2{(0,a+p 2,b)(1,m+a+p 2,a(m+a)+b):b∈Fp} ω(GP)=⋃ m<p/2{(1,m,a(m+a)) :a≥p 2}, If a0(m+a0)=a1(m+a1), then (a0+a1)(m+a0+a1)=0. Hence, a1=a0or a1=m+a0. In both cases, a0,a1<p/2 or a0,a1≥p/2 when m<p/2. Hence, ω(GL)∩ω(GP)= ∅. This proves that the p 2-regular graphs GLand GPare suitable for amalgamation into Cq.ByTheorem 2.1, the graph Cq(GL,GP) is (q+p 2)-regular with girth at least five and order 2q2.■ Before proceeding to obtain more accurate bounds, let us notice that no Cayley color (0,0, β) appears in the set ω(GL)∪ω(GP), where GLand GPare the graphs constructed in Theorem 3.1 and in Theorem 3.3. 4. Refined bounds We are now interested in increasing the degree of the graphs GLand GPconstructed in Section 3. The technique involves a recursive construction with two pairs of graphs, one to be amalgamated into ˜ GLand the other into ˜ GP. Proposition 4.1. Let s ≥3and p =2s. If q =2p2, let K, rL, rPbe defined as in Theorem 3.1; and if q =p2, let rL, rPbe defined as in Theorem 3.3. Assume that H0 L, H1 L, H0 P, H1 Pare graphs with vertex set Fpand girth g ≥5. Additionally, consider (i) H0 L, H1 Lhave common degree sL. (ii) H0 P, H1 Phave common degree sP. (iii) The sets of Cayley colors of H0 L, H1 L, H0 P, H1 Pare pairwise disjoint in Fp. Then, there exists a pair of suitable graphs GL, GPwith vertex set Fqand degrees rL+sL, rP+sPrespectively. 6 E. Abajo and M. Bendala Fig. 1. One pair of graphs H0 Land H1 Lwith disjoint Cayley colors in F16. Proof. Consider the bijections ΦL,ΦPand the graphs ˜ GL,˜ GPprovided in Theorem 3.1 for q=2p2,orinTheorem 3.3 for q=p2. By (i) and (iii), the pair H0 L,H1 Lis suitable for amalgamation into Cp, then also into its subgraph ˜ GL. Similarly, by (ii) and (iii), the pair H0 P,H1 Pcan be suitably amalgamated into ˜ GP. In order not to introduce more notation, let ˜ GLand ˜ GP also denote the graphs resulting after these amalgamations. In the same way, let GLand GPhold for the graphs isomorphic to ˜ GLand ˜ GPafter applying the bijections ΦLand ΦP. These new graphs GLand GPhave girth 5 and degrees rL+sLand rP+sP, respectively. The colors in Fqof the new edges of GLand GPform the subsets {(0,0, β):β∈ω(H0 L)∪ω(H1 L)},{(0,0, β):β∈ ω(H0 P)∪ω(H1 P)}of Fq, respectively. By (iii) both sets are disjoint. Also, as we have mentioned above, these colors are different from the original ones of GLand GP. Hence, the new pair GL,GPis suitable for amalgamation into Cq.■ Proposition 4.1 allows a slight improvement of Theorems 3.1 and 3.3. There is an easy way to construct the four graphs required in this proposition. Lemma 4.1. Let s ≥3and p =2s. Assume HL, HPare graphs with vertex set Fp/2, girth g ≥5, degrees sL, sP, and sharing no Cayley color. Then, there exist four graphs H0 L, H1 L, H0 P, H1 Pverifying the hypothesis of Proposition 4.1. Proof. Let us identify F+ p≈F+ p/2⊕F+ 2. Define graphs H0 L,H1 Lwith vertex set Fpand edge sets E(H0 L)= {(u,0)(v, 0) :uv∈E(HL)}∪{(u,1)(v, 1) :uv∈E(HL)} E(H1 L)= {(u,0)(v, 1) :uv∈E(HL)}∪{(u,1)(v, 0) :uv∈E(HL)} Similarly, define graphs H0 P,H1 P. It is straightforward to see that H0 L,H1 L,H0 P,H1 Psatisfy the hypothesis of Proposition 4.1.■ 5. Small cases We apply the refined bounds described in Section 4to some particular cases. Moreover, we also describe an iterative process that makes feasible to provide better bounds. In [1] the authors construct two pairs of suitable graphs with vertex sets F25and F26with degrees 5 and 6 respectively. Consequently, bounds n(32 +5,5) ≤2·322and n(64 +6,5) ≤2·642were established. In [2], (see Table 2 and inequality (2) in Remark 2.1), thanks to suitable amalgamations into the elliptic semiplanes L127 and L257, the bounds n(127 +10 −1,5) ≤2(127 +1−1)(127 −1) =32004 and n(257 +12 −3,5) ≤2(257 +1−3)(257 −1) =130560 were established. In this paper we get the less accurate bounds n(27+8,5) =n(136,5) ≤2·(27)2−27=32640 and n(28+10,5) =n(266,5) ≤2·(28)2−28=130816. Let us continue with some more values. •q=29=512 We have q=2p2with p=24. Let us represent the elements of F16 by the integers 0, . . . , 15 and consider that F16 ≃F2[X]/(X4+X+1). Computations lead to the value K=6 and, by Theorem 3.1, there is a suitable pair of regular graphs with degrees rL=rP=15. To increase the degree of these graphs consider the 3-regular graphs H0 L,H1 Ldisplayed in Fig. 1 and the 2-regular graphs H0 P,H1 Pin Fig. 2. They have girth 6 and 8 respectively. Since ω(H0 L)= {1,2,4,8},ω(H1 L)= {7,11,13,14}, ω(H0 P)= {3,6,12}and ω(H1 P)= {5,9,10}any two of these graphs have disjoint sets of colors in Fp. 7 E. Abajo and M. Bendala Fig. 2. Another pair of graphs H0 Pand H1 Pwith disjoint Cayley colors in F16. Fig. 3. (4,6)-graphs H0 Land H1 Lwith disjoint Cayley colors in F32. Using Proposition 4.1 we construct graphs GL,GPof degrees 18, 17 respectively, suitable for amalgamation into C29. According to Theorem 2.2, we have the bound n(29+17) ≤2·(29)2−29=2·29(29−1 2) and, more generally, n(k,5) ≤2·29(k−17 −1 2) for k≤29+17. Actually, this is a record bound when 29+5≤k≤29+17. •q=210 =1024 Now q=p2with p=25=32. By Theorem 3.3, there is a suitable pair of regular graphs with degrees rL=rP=16. Consider the (4,6)-regular graphs H0 L,H1 Lin Fig. 3 and the (3,6)-regular graphs H0 P,H1 Pin Fig. 4. The sets of Cayley colors in F32 are ω(H0 L)= {1,7,11,15,23,27,31},ω(H1 L)= {3,5,9,13,21,25,29},ω(H0 P)= {17,18,20,24}, ω(H1 P)= {2,4,6,8,10,12,14,16,22,26,28,30}. Any two of these sets are disjoint. By using Proposition 4.1 we construct the new suitable pair of graphs GL,GPwith degrees 20, 19 respectively. Theorem 2.2 states n(210 +19) ≤2·210(210 −1 2) and the new record bound n(k,5) ≤2·210(k−19 −1 2) for 210 +16 ≤k≤210 +19. •q=211 =2048 Again, p=25. Computations in F32 ≃F2[X]/(X5+X2+1) lead to the value K=11. By Theorem 3.1 there are two suitable graphs GL,GPof degrees 3p/4+⌈K/2⌉ = 30 and 3p/4+⌊K/2⌋ = 29. By using again the graphs H0 L,H1 L,H0 P,H1 Pprovided in Figs. 3 and 4together with Proposition 4.1 we construct the new suitable 33-regular graphs GL,GP.Theorem 2.1 establishes the new record bound n(k,5) ≤2·211(k−33) for 211 +3≤k≤211 +33. •q=212 =4096 Now p=26=64 and q=p2. In [1] the authors give a pair of suitable graphs with vertex set F25and degree 5. By Lemma 4.1, there are four graphs with vertex set F26verifying the hypothesis of Proposition 4.1. Then, by Theorem 3.3, we obtain a suitable pair of graphs GLand GP, both with degree 26/2+5=37, and the associated bound n(212 +37,5) ≤2(212)2. 8 E. Abajo and M. Bendala Fig. 4. (3,6)-graphs H0 Pand H1 Pwith disjoint Cayley colors in F32. We summarize the last results: Theorem 5.1. The following upper bound on the minimum order of a (k,5)-graph holds q k rec(k,5) 2929+5≤k≤29+17 2 ·29(k−17 −1 2) 210 210 +16 ≤k≤210 +19 2 ·210(k−19 −1 2) 211 211 +3≤k≤211 +33 2 ·211(k−33) 212 212 +29 ≤k≤212 +37 2 ·212(k−37) Alternating Theorems 3.2 and 3.3, the process used for q=212 could indefinitely be applied to obtain refined bounds associated to greater powers of two. Declaration of competing interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. References [1] E. Abajo, G. Araujo-Pardo, C. Balbuena, M. Bendala, New small regular graphs of girth 5, Discrete Math. 340 (8) (2017) 1878–1888. [2] E. Abajo, C. Balbuena, M. Bendala, X. Marcote, Improving bounds on the order of regular graphs of girth 5, Discrete Math. 342 (10) (2019) 2900–2910. [3] M. Abreu, G. Araujo-Pardo, C. Balbuena, D. Labbate, Families of small regular graphs of girth 5, Discrete Math. 312 (2012) 2832–2842. [4] C. Balbuena, Incidence matrices of projective planes and other bipartite graphs of few vertices, SIAM J. Discrete Math. 22 (4) (2008) 1351–1363. [5] J.A. Bondy, U.S.R. Murty, Graph Theory, in: Springer Series: Graduate Texts in Mathematics, vol. 244, 2008. [6] A. Cronheim, T-groups and their geometry, Illinois J. Math. 9 (1965) 1–30. [7] P. Dembowski, Finite Geometries, Springer, Berlin Heidelberg New York, 1968, (reprint 1968). [8] M. Funk, Girth 5 graphs from elliptic semiplanes, Note Mat. 29 (Suppl. 1) (2009) 91–114. [9] A.J. Hoffman, R.R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. (1960) 497–504. [10] L.K. Jørgensen, Girth 5 graphs from relative different sets, Discrete Math. 293 (2005) 177–184. [11] H. Lüneburg, Charakterisierungen der endlichen desarguesschen projektiven Ebenen, Math. Z. 85 (1964) 419–450. [12] M. O’Keefe, P.K. Wong, A smallest graph of girth 5 and valency 6, J. Combin. Theory Ser. B 26 (1979) 145–149. [13] N. Robertson, The smallest graph of girth 5 and valency 4, Bull. Amer. Math. Soc. 70 (1964) 824–825. [14] G. Wegner, A smallest graph of girth 5 and valency 5, J. Combin. Theory Ser. B 14 (1973) 203–208. [15] P.K. Wong, On the uniqueness of the smallest graphs of girth 5 and valency 6, J. Graph Theory 3 (1978) 407–409. [16] Y.S. Yang, C.X. Zhang, A new (5,5)-cage and the number of (5,5)-cages, J. Math. Res. Exposition 9 (1989) 628–632 (in Chinese). 9