New small regular graphs of girth 5

New small regular graphs of girth 5 E. Abajoa, G. Araujo-Pardob, C. Balbuenac,*, M. Bendalaa aDepartamento de Matemática Aplicada I, Universidad de Sevilla, Spain bInstituto de Matemáticas, Universidad Nacional Autónoma de México, México D. F., Mexico cDepartament 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 25 June 2016 Received in revised form 21 February 2017 Accepted 26 March 2017 Available online 21 April 2017 Keywords: Small regular graphs Cage Girth Amalgam 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. The cage problem consists of constructing (k,g)-graphs of minimum order n(k,g). We focus on girth g=5, where cages are known only for degrees k≤7. We construct (k,5)-graphs using techniques exposed by Funk (2009) and Abreu et al. (2012) to obtain the best upper bounds on n(k,5) known hitherto. The tables given in the introduction show the improvements obtained with our results. 1. Introduction All the graphs considered are finite and simple. Let Gbe a graph with vertex set V=V(G) and edge set E=E(G). The girth of a graph Gis the size g=g(G) of a shortest cycle. The degree of a vertex v∈Vis the number of vertices adjacent to v. A graph is called k-regular if all its vertices have the same degree k, and bi-regular or (k1,k2)-regular if all its vertices have either degree k1or k2. 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; the order of a (k,g)-cage is denoted by n(k,g). Cages were introduced by Tutte [29] in 1947 and their existence was proved by Erdős and Sachs [14] in 1963 for any values of regularity and girth. The lower bound on the number of vertices of a (k,g)-graph is denoted by n0(k,g), and it is calculated using the distance partition either to a vertex (for odd g), or to an edge (for even g): 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. A graph that attains this lower bound is called a Moore (k,g)-cage. Biggs [11] calls excess of a (k,g)–graph Gthe difference |V(G)| − n0(k,g). There has been intense work related with the cage problem, focused on constructing the smallest (k,g)- graphs (for a complete survey of this topic see [16]). In this paper we are interested in the cage problem for g=5, in this case n0(k,5) =1+k2. It is well known that this bound is attained for k=2,3,7 and perhaps for k=57 (see [11]) and that for k=4,5,6, the known graphs of minimum order are cages (see [22–25,30–33]). *Corresponding author. E-mail addresses: [email protected] (E. Abajo), [email protected] (G. Araujo-Pardo), [email protected] (C. Balbuena), [email protected] (M. Bendala). http://dx.doi.org/10.1016/j.disc.2017.03.020 0012-365X/ 1879 Table 1 Current and our new values of rec(k,5) for 8 ≤k≤22. k rec(k,5) Due to Reference New rec(k,5) 8 80 Royle, Jørgensen [20,26] 9 96 Jørgensen [20] 10 124 Exoo [15] 11 154 Exoo [15] 12 203 Exoo [15] 13 230 Exoo [15] 14 284 Abreu et al. [1] 15 310 Abreu et al. [1] 16 336 Jørgensen [20] 17 448 Schwenk [27]436 18 480 Schwenk [27]468 19 512 Schwenk [27]500 20 572 Abreu et al. [1]564 21 682 Abreu et al. [1]666 22 720 Jørgensen [20]704 Table 2 Current and our new values of rec(k,5) for 32 ≤k≤52. k rec(k,5) Due to Reference New rec(k,5) 32 1680 Jørgensen [20]1624 33 1856 Funk [17]1680 34 1920 Jørgensen [20]1800 35 1984 Funk [17]1860 36 2048 Funk [17]1920 37 2514 Abreu et al. [1]2048 38 2588 Abreu et al. [1]2448 39 2662 Abreu et al. [1]2520 40 2736 Jørgensen [20]2592 41 3114 Abreu et al. [1]2664 42 3196 Abreu et al. [1]2736 43 3278 Abreu et al. [1]3040 44 3360 Jørgensen [20]3120 45 3610 Abreu et al. [1]3200 46 3696 Jørgensen [20]3280 47 4134 Abreu et al. [1]3360 48 4228 Abreu et al. [1]3696 49 4322 Abreu et al. [1]4140 50 4416 Jørgensen [20]4232 51 4704 Jørgensen [20]4324 52 4800 Jørgensen [20]4416 Jørgensen [20] established that n(k,5) ≤2(q−1)(k−2) for every odd prime power q≥13 and k≤q+3. Abreu et al. [1] proved that n(k,5) ≤2(qk −3q−1) for any prime q≥13 and k≤q+3, which improved Jørgensen’s bound except for k=q+3 where both coincide. In [17] Funk uses a technique that consists in finding regular graphs of girth greater or equal than five and performing some operations of amalgams and reductions of the (bipartite) incidence graph, also called Levi Graph of elliptic semiplanes of type Cand L(see [5,13,17]). In this paper we improve some results of Funk finding the best possible regular graphs to amalgamate which allow us to obtain new better upper bounds. To do that, we also use the techniques given in [1,2] where the authors amalgamate not only regular graphs, but also bi-regular graphs. In this paper new small (k,5)-graphs are constructed for 17 ≤k≤22 using the incidence graphs of elliptic semiplanes of type C. The new upper bounds appear in the last column of Table 1, which also shows the current values for 8 ≤k≤22. To evaluate our achievements, we follow the notation in [16,17], and let rec(k,5) denote the smallest currently known order of a k-regular graph of girth 5. Hence n(k,5) ≤rec(k,5). For 23 ≤k≤31, the value rec(k,5) obtained by Funk in [17] remain untouched. However, for 32 ≤k≤52, we construct ak-regular graph of girth five and provide in Table 2 a new value of rec(k,5). Finally, when q≥49 is a prime power, the search for 6-regular suitable pairs of graphs allows us to establish the two following general results. Note that the bounds are different depending on the parity of q. Theorem 1.1. Given an integer k ≥53, let q be the lowest odd prime power such that k ≤q+6. Then n(k,5) ≤2(q−1)(k−5). Theorem 1.2. Given an integer k ≥68, let q =2mbe the lowest even prime power such that k ≤q+6. Then n(k,5) ≤2q(k−6). Since the bounds of Theorems 1.1 and 1.2, associated to primes q=49 and q=64, represent a considerable improvement to the current known ones, we give them explicitly in Table 3. 1880 Table 3 Current and our new values of rec(k,5) for k=55,70. k rec(k,5) Due to Reference New rec(k,5) 55 5510 Abreu et al. [1]4800 70 8976 Jørgensen [20]8192 To finalize the introduction we want to emphasize that Funk, in [17], gives a pair of 4-regular graphs of girth 5 suitable for amalgamation into some specific incidence graphs of elliptic semiplanes and he posed the question about the existence of a suitable pair of 5-regular graphs for the same objective. In this paper we exhibit these graphs which solve this open question. Furthermore, let us notice that all the bounds on n(k,5) contained in this paper are obtained constructively, that is, for each k, we construct a (k,5)-graph with improved order rec(k,5). 2. Preliminaries A useful tool to construct k-regular graphs of girth 5 is the operation of amalgamation on the incidence graph of an elliptic semiplane (Jørgensen [20] and Funk [17]). Let qbe a prime power and consider the Levi graphs or incidence graphs Cqand Lqof elliptic semiplanes of type Cand L, respectively. Recall that a semiplane of type Cis obtained from the projective plane of order qby choosing an incident point line pair (p, ℓ) and deleting all the lines incident with pand all the points belonging to ℓ. Thus, the Levi (or incidence) graph Cqis bipartite, q-regular and has 2q2vertices, which correspond in the elliptic semiplane of type Cto q2points and q2lines both partitioned into qparallel classes or blocks of qelements each. A semiplane of type Lis obtained from the projective plane of order qby choosing a non-incident point line pair (p, ℓ) and deleting all the lines incident with pand all the points belonging to ℓ. Hence, the Levi graph Lqis also bipartite, q-regular and has 2(q2−1) vertices, which correspond in the elliptic semiplane of type Lto q2−1 points and q2−1 lines both partitioned into q+1 parallel classes of q−1 elements each. To construct our new graphs we find regular and bi-regular graphs of girth greater or equal than five and we use them to perform some operations of amalgams and reductions in Cqor Lq. In [20], Jørgensen exploits these ideas and proves that two graphs are suitable for amalgamation (one of them in each block of points and the other in each block of lines) if they have disjoint sets of Cayley colors. In [1] these ideas are also used to construct graphs using the elliptic semiplane of type C, and the main theorem of [1] was refined in [2] to construct bi-regular cages of girth 5. In fact, the suitable graphs to be amalgamated can have some specific edges with a common Cayley color. The paper is organized as follows. In the next section we work with elliptic semiplanes of type Cand with techniques used in [1,2]. In Section 4we work with elliptic semiplanes of type Land with techniques given by Funk in [17]. Finally, in Section 5we return to the elliptic semiplanes of type Cfor even prime powers because new descriptions are required. 3. Amalgamating into elliptic semiplanes of type C Let qbe a prime power and Fqthe finite field of order q; we recall the definition and properties of the incidence bipartite graph Cqof an elliptic semiplane of type Cexactly as they appear in [1,2]. Notice that in these papers the authors call this graph Bqand here, as it is related to the elliptic semiplane of type C, we prefer to call it Cq. Definition 3.1. Let Cqbe a bipartite graph with vertex set (V0,V1) where Vr=Fq×Fq,r=0,1; and edge set defined as follows: (x,y)0∈V0adjacent to (m,b)1∈V1if and only if y=mx +b.(1) The graph Cqis also known as the incidence graph of the biaffine plane [18] and it has been used to find extremal graphs without short cycles (see [1–10,21]). The graph Cqis q-regular of order 2q2, has girth g=6 for q≥3 and it is vertex transitive. The set of vertices can be described as the disjoint union of the sets Px= {(x,y)0:y∈Fq}and Lm= {(m,b)1:b∈Fq}for all x,m∈Fq. Other well known properties of the graph Cqcan be seen in [1,2,18,21]. Let Γbe a subgraph of G, and Γ′a graph of the same order of Γand with the same labels on their vertices; an amalgam of Γ′into Γis a graph obtained from Gby adding all the edges of Γinto Γ′. In [1] the authors described a technique of amalgamation of two r-regular graphs H0,H1and two (r,r+1)-regular graphs G0,G1(all of them of girth at least 5 and with some specific properties) into a subgraph of Cqsuch that the resulting amalgam graph, denoted by Cq(H0,H1,G0,G1), is (q+r)-regular and has girth at least five. Recall that if Gis a graph with V(G) labeled with the elements of Fqand αβ is an edge of G, then the Cayley Color or weight of the edge αβ is ±(α−β)∈Fq− {0}.Theorem 3.1 is a reformulation of Theorem 5 in [1] (with a new strong hypothesis that also appears in Theorem 4.9 in [2]). Theorem 3.1. Let q ≥3be a prime power and r ≥2an integer. Consider graphs H0, H1, G0and G1with the following properties: (i) V(Gi)=Fqand Giis an (r,r+1)-regular graph of girth g(Gi)≥5for i =0,1; 1881 Fig. 1. The graphs Hiand Gifor i=0,1 where q=16. (ii) Hiis an r-regular graph of girth g(Hi)≥5and V(Hi)= {v∈Fq:dGj(v)=r with i = j}, for i,j∈ {0,1}. (iii) E(H0)∩E(H1)= ∅, E(H0)∩E(G1)= ∅, E(H1)∩E(G0)= ∅and G0and G1have disjoint Cayley colors. Let Cqbe the graph given in Definition 3.1, and A =V(Cq)\({(0,y)0:y∈ V(H0)}∪{(0,b)1:b∈ V(H1)}). Let Cq[A]be the induced subgraph of Cqby A. Let the sets of edges E0(0) = {(0,y)0(0,y′)0:yy′∈E(H0)}, E1(0) = {(0,b)1(0,b′)1:bb′∈E(H1)},E0(x)= {(x,y)0(x,y′)0: yy′∈E(G0)},E1(m)= {(m,b)1(m,b′)1:bb′∈E(G1)}for all m,x∈Fq−{0}. The graph Cq(H0,H1,G0,G1)with vertex set A and edge set E(Cq[A])∪(⋃x∈FqE0(x)) ∪(⋃m∈FqE1(m)) is (q+r)-regular and has girth at least five. The proof is the same as the one of Theorem 4.9 in [2]. Notice that Theorem 3.1 can also be applied when G0and G1are regular graphs (then H0=G0and H1=G1). In this case we denote the obtained graph by Cq(G0,G1). Next, for q∈ {16,17,19}, we construct graphs H0,H1,G0,G1, satisfying the conditions of Theorem 3.1. Construction 1: •For q=16: Let (F16,+)∼ =((Z2)4,+) be a finite field of order 16 with set of elements {(d,e,f,g):d,e,f,g∈Z2}, we write defg instead of (d,e,f,g). Consider the graphs H0,H1,G0and G1displayed in Fig. 1. The graphs G0and G1are not isomorphic, although both have girth 5 and order 16, with 6 vertices of degree 4 and 10 vertices of degree 3. We label the vertices of G0and G1such that the vertices of the set S= {0000,1100,0110,1001,0011,1111}have degree four and the other ones have degree three. The weights or Cayley colors of G0(and G1) are {0001,0010,0100,1000,1111}(and {0011,0110,0111,1001,1010,1011,1100,1101,1110}, respectively). Hence, G0and G1have disjoint sets of Cayley colors. Moreover, the graphs H0and H1are isomorphic to the Petersen graph and they are labeled with the elements of (Z2)4−S in such a way that E(H0)∩E(H1)= ∅,E(H0)∩E(G1)= ∅and E(H1)∩E(G0)= ∅. •For q=17: Let H0,H1,G0and G1be the graphs of girth 5 displayed in Fig. 2. Graphs G0and G1are isomorphic with V(G0)=V(G1)= Z17, and both have the same set of vertices S= {0,2,5,8,10,13,15}of degree 4. The Cayley colors of G0(and G1) in Z17 are ±{1,5,8}(and ±{2,3,4,6,7}, respectively). Regarding H0and H1, it can be checked that V(H0)=V(H1)=Z17 −S, E(H0)∩E(H1)= ∅,E(H0)∩E(G1)= ∅and E(H1)∩E(G0)= ∅. 1882 Fig. 2. The graphs Hiand Gifor i=0,1 where q=17. •For q=19: Let H0,H1,G0and G1be the graphs of girth 5 shown in Fig. 3. Graphs G0and G1are isomorphic, V(G0)=V(G1)=Z19 and both have the same set S= {0,2,3,5,6,12,13,16,17}of vertices degree 4. The weights or Cayley colors modulo 19 of G0(and G1) are ±{1,4,7,8}(and ±{2,3,5,6,9}, respectively). The two graphs H0and H1have vertex set Z19 −Sand verify E(H0)∩E(H1)= ∅,E(H0)∩E(G1)= ∅and E(H1)∩E(G0)= ∅. Next, we apply Theorem 3.1 to q∈ {16,17,19}. The graph Cq(H0,H1,G0,G1) is a (q+3,5)-regular graph with less vertices than any other (q+3)-regular graph of girth 5 so far known, and therefore the upper bound rec(k,5) for k∈ {19,20,22}is improved. As it is explained in the Reduction 2 in [1], referred as ‘‘Deletion’’ in [17], by removing pairs of blocks Pxand Lm from Cq(H0,H1,G0,G1), we also generate new graphs which improve rec(k,5) for k∈ {17,18,21}. Theorem 3.2. The following upper bound rec(k,5) on the order n(k,5) of a k-regular cage of girth 5holds k17 18 19 20 21 22 rec(k,5) 436 468 500 564 666 704 Proof. Usingthegraphs given inConstruction1, we obtainfor q∈ {16,17,19}the graphCq(H0,H1,G0,G1) as inTheorem 3.1, which has girth 5. Moreover we have the following considerations: For q=16, C16(H0,H1,G0,G1) is a (19,5)-graph of order 2 ·162−12 =500 implying that any (19,5)-cage has at most 500 vertices. Removing of C16(H0,H1,G0,G1) (using the operation called ‘‘Reduction 2’’ in [1]) a block of lines Lmand a block of points Px, for x,m∈(Z2)4−{0000}, we construct a 18-regular graph with 500 −2·16 =468 vertices. Similarly, deleting from this last graph another pair of blocks we obtain a 17-regular graph of girth 5 with 436 vertices. Each of these k-regular graphs (k=17,18,19) has 12 vertices less than the ones constructed by Schwenk in [27]. For q=17, C17(H0,H1,G0,G1) is a (20,5)-graph of order 2 ·172−14 =564, which implies that a (20,5)-cage has at most 564 vertices. For q=19, C19(H0,H1,G0,G1) is a (22,5)-graph of order 2 ·192−18 =704, which also implies that any (22,5)-cage has at most 704 vertices. Newly, deleting any block of points and any block of lines (except P0and L0blocks), it is straightforward to check out that n(21,5) ≤666. ■ Remark 3.1. Note that the constructionof a (q+3)-regular graph of girth atleast 5 using bi-regular amalgams into a subgraph of Cqinvolves the existence of two 3-regular graphs H0and H1and two (3,4)-regular graphs G0and G1all of them with girth at least 5. The graph Cq(H0,H1,G0,G1) has order 2(q2−(q−n(H0))) ≥2(q2−q+10). It means that our construction is the 1883 Fig. 3. The graphs Hiand Gifor i=0,1 where q=19. best possible one for q=16 and q=17, because a 4-regular amalgam could only be possible for q≥n(4,5) =19 (the (4,5)-cage is the Robertson Graph that has order 19). 4. Elliptic semiplanes of type L In this section we use the technique given by Funk in [17] to amalgamate a pair of suitable regular graphs into the Levi graph Lqof an elliptic semiplane of type L. Recall that the semiplane of type Lis obtained by deleting from the projective plane of order qa non-incident pair (p, ℓ), all the lines incident with the point pand all the points incident with the line ℓ. Moreover, the Levi graph Lqis bipartite, q-regular and has 2(q2−1) vertices of which q2−1 are points and q2−1 are lines in the elliptic semiplane, both partitioned into q+1 parallel classes of q−1 elements each. We divide the section into two parts. First we construct suitable regular graphs G0,G1and then we describe the graph Lq(G0,G1) obtained after amalgamation. 4.1. Constructions of regular graphs of girth five To apply Funk’s technique we need to construct two regular graphs with the same order, girth at least five and having disjoint Cayley colors, one of them to be amalgamated into the point blocks and the other into the line blocks of Lq. Let Znbe the set of integers modulo n, and J= {k1,...,kw} ⊂ Zn− {0}. Recall that a circulant graph Zn(J) is a graph with vertex set Znand edges αβ where β−α∈J. Let n=2tand suppose that every element of Jis odd. We denote by S2t(k1, . . . , kw) the subgraph of the circulant graph Z2t(k1, . . . , kw) with vertex set Z2tand edge set {{2v, 2v+kj} : 0≤v≤ t−1,1≤j≤w}where the sum is taken modulo 2t. Moreover, we denote by S∞(k1, . . . , kw) the (infinite) graph defined in a similar way over Z. Next, we describe some relevant properties of this graph. Lemma 4.1. Given an integer t ≥5, and a sequence k1, . . . , kwof different odd elements from Z2t, the graph S2t(k1, . . . , kw)is w-regular, bipartite and has at most wCayley colors in Z2t. Moreover, the girth of S2t(k1, . . . , kw)is at least 6iff all the numbers ki−kjare different for i = j and 1≤i,j≤w. These properties hold even for 2t= ∞. Proof. Given an odd element kj∈Z2t, the set of edges {{2v, 2v+kj} : 0≤v≤t−1}defines a matching between the vertices with even label and the ones with odd label in Z2t. Therefore, for a given sequence k1, . . . , kwof different odd elements of Z2t, the graph G=S2t(k1, . . . , kw) is w-regular, bipartite and has even girth g≥4. 1884 By hypothesis, the numbers ki−kjare different for i= jand 1 ≤i,j≤w. We prove that the girth of Gis greater or equal than 6. Suppose that there exists a 4-cycle v0v1v2v3v0. By reordering, we may take v0,v2even and v1,v3odd. So, v1=v0+ki, v2=v1−kj,v3=v2+kp,v0=v3−kqwith i= j,p= q,p= j,q= i.Then, ki−kj+kp−kq=0 and ki−kj=kq−kp in Z2twhich is a contradiction, since by hypothesis all these numbers are different. Hence the girth of Gmust be at least 6 because it is bipartite. The proof is the same when Z2t=Z, taking into account that in this case the equalities are considered in Z.■ The (q+1,6)-cages with qa prime power, are known examples of this type of graphs. For instance, the Heawood graph or the Moore (3,6)-cage can be constructed as S14(1,−1,5). It is also very known that Moore (q+1,6)-cages can also be represented by using perfect difference sets (see [20,28]) and as the Levi graphs of the projective plane over the field Fq. Definition 4.1. Given an integer t≥5, a sequence of different odd elements k1, . . . , kwand two different even elements 0<P,Q<tfrom Z2t, we denote by S2t(P,Q;k1, . . . , kw) the graph obtained by adding to S2t(k1, . . . , kw) the new edges {2v, 2v+P}and {2v+1,2v+1+Q}, where the sum is taken modulo 2t. The graph S∞(P,Q;k1, . . . , kw) is defined in a similar way over Z. Notice that if Pdivides 2t, the subgraph of S2t(P,Q;k1, . . . , kw) induced by the even numbers is formed by P/2 cycles, each of them with size 2t/P. Similar result holds when Qdivides 2tand the subgraph of S2t(P,Q;k1, . . . , kw) induced by the odd numbers. The standard Generalized Petersen Graphs with 2tvertices introduced by Coxeter in [12] are obtained as S2t(2,Q;1) and the I-graph I(t,j,k) in [34] as S2t(2j,2k;1). Funk uses in [17] a 4-regular generalization P(k, η, ν) of the Petersen graph which corresponds to S2k(2,2η;1,2ν+1). Another example is one of the four (5,5)-cages on 30 vertices, which can be described as S30(6,12;1,−1,9). It can be checked that this graph is isomorphic to the (5,5)-cage obtained from Hoffman–Singleton graph by deleting two Petersen graphs. Next, we prove some useful properties of these graphs. Lemma 4.2. The graph S2t(P,Q;k1, . . . , kw)defined over Z2tis (w+2)-regular and has at most w+2Cayley colors. Moreover, the girth of S2t(P,Q;k1, . . . , kw)is at least 5 if and only if the following conditions hold: (i) The numbers 3P,4P,3Q,4Q are different from 0in Z2t. (ii) All the numbers ki−kjare different for i = j and 1≤i,j≤w. (iii) No relation ki−kj=a−a′holds for any pair a,a′∈Ω= {0,±P,±Q}. The result also holds when Z2t=Z. Proof. According to Lemma 4.1, the graph B=S2t(k1, . . . , kw) is an w-regular bipartite graph with girth at least 6 iff item (ii) is satisfied. The partite sets of Bare the set of even vertices, denoted by Ev, and the set of odd vertices, denoted by Od, of Z2t. Consider T0and T1the circulant graphs whose vertices are Evand Od respectively, and whose edges are {2v, 2v+P} and {2v+1,2v+1+Q}, respectively. Clearly, T0and T1are 2-regular and condition (i) that 3P,4P,3Q,4Q= 0 means that T0and T1have girth at least five. Denote G=S2t(P,Q;k1, . . . , kw) and observe that the graph Gis an amalgamation B(T0,T1) obtained by adding to Evall the edges of T0and by adding to Od all the edges of T1. Hence Gis (w+2)-regular. Let us see that Ghas girth five. Suppose that Cis a cycle in Gof size 3 or 4 which must contain even and odd vertices. If Chas only one even vertex, then ki−kj+a=0 for a∈ {±Q,±2Q}, depending on the size of C, contradicting (iii). If Ccontains two even and two odd vertices, we have ki+a−kj−a′=0, for a,a′∈ {±P,±Q}, again contradicting (iii). Therefore Ghas girth at least 5 iff conditions (i), (ii), (iii) are satisfied. ■ Notice that it is useful to take Q=2Pbecause in this case there are only four differences ±{P,2P,3P,4P}to be avoided. Furthermore, if S2t(P,Q;k1, . . . , kw) has girth g≥5, the (infinite) graph S∞(P,Q;k1, . . . , kw) also satisfies g≥5. We are interested in the converse result. Definition 4.2. We call span Dof a graph S∞(P,Q;k1, . . . , kw) the maximum element of the set {|ki|,ki−kj,a−a′}, with a,a′∈ {0,±P,±Q}. Lemma 4.3. Let P = Q be two positive even integers and k1, . . . , kwdifferent odd integers. Consider a graph S∞(P,Q;k1, . . . , kw) with girth g ≥5and span D. If t ≥D+1, then S2t(P,Q;k1, . . . , kw)is (w+2)-regular and has girth at least 5. Proof. By definition, 0 <P,Q≤Dand −D≤ki≤D. As t≥D+1, then 0 <P,Q,|k1|, . . . , |kw|<tand clearly S2t(P,Q;k1, . . . , kw) is (w+2)-regular. Let us see that S2t(P,Q;k1, . . . , kw) has girth g≥5. Since S∞(P,Q;k1, . . . , kw) has girth g≥5, it follows that ki−kj= kp−kqin Z. Also, from the definition of D, we have −D≤ki−kj,kp−kq≤D, yielding that −2t<(ki−kj)−(kp−kq)<2t. Hence, ki−kj= kp−kqin Z2t. The same argument shows ki−kj= a−a′in Z2tfor a,a′∈ {±P,±Q}. These are the requirements (ii), (iii) of Lemma 4.2. Notice that (i) of Lemma 4.2 has been explicitly stated, since 2t≥2(D+1) ≥max{2(2P+1),2(2Q+1)}, which implies that 3P,4P,3Q,4Qare different from 0 in Z2t.■ As an example, let us mention that the graph S∞(2,4;3,−7) has girth 5 and span D=10. Therefore, the graph S2t(2,4;3,−7) is a 4-regular with girth 5 for orders 2t≥22. In the next subsection we construct a pair of regular graphs of girth 5 suitable for amalgamation into Lqfor some prime powers q. 1885 4.2. Amalgamating into elliptic semiplanes of type L Following the terminology of Funk in [17] we say that two r-regular graphs G0and G1with girth at least five are suitable for amalgamation into the elliptic semiplane Lqif they are labeled with the elements of the cyclic group (Zq−1,+) with disjoint sets of Cayley colors in this group. When qis odd, the fact that Zq−1has q−1 elements suggests the use of this semiplane, because r-regular graphs with odd degree have even order. As in Section 4, the amalgamation of a pair of r-regular suitable graphs into the elliptic semiplane Lqgives a (q+r,5)- graph Lq(G0,G1). It has 2(q2−1) vertices and deleting pairs of blocks of vertices from Lq(G0,G1), for regularities k≤q+r, we have n(k,5) ≤2(q−1)(k−r+1).(2) For q=19 there is a unique 4-regular graph with girth 5, the (4,5)-cage due to Robertson in [24]. The use of the highest value of r≥4 for a given q>19 increases the accuracy of the inequality (2). Funk in [17] constructs the best possible regular amalgams for q∈ {23,25,27}. Next, we give a construction of graphs which provide accurate amalgams for q∈ {29,31,37,41,43,47}. Construction 2: •For q=29: Consider the graphs G0=S28(4,8;1,−1) and G1=S28(2,6;3,−7). It is a suitable pair, that is, both graphs are 4-regular, have girth five and have disjoint sets of Cayley colors, concretely ±{1,4,8}and ±{2,3,6,7}, respectively. Hence, the 33- regular graph L29(G0,G1) has girth 5, order 1680 and diameter 4. Deletion provides entries k=32,33 of Table 2. •For q=31: There exist four (5,5)-cages (see [22,25,30,32,33]) one of them being the graph G0=S30(6,12;1,−1,9). Another graph G1has been found with the following relabeling of the vertices. G0↔G1G0↔G1G0↔G1G0↔G1G0↔G1G0↔G1 0↔0 1 ↔28 2 ↔1 3 ↔27 4 ↔2 5 ↔19 6↔4 7 ↔7 8 ↔5 9 ↔22 10 ↔6 11 ↔3 12 ↔8 13 ↔24 14 ↔9 15 ↔20 16 ↔10 17 ↔15 18 ↔12 19 ↔23 20 ↔13 21 ↔11 22 ↔14 23 ↔29 24 ↔16 25 ↔21 26 ↔17 27 ↔25 28 ↔18 29 ↔26 Since the Cayley colors of G1are the elements of the set Z30 −{0,±1,±6,±9,±12}, the graphs G0and G1have disjoint Cayley colors, and therefore, L31(G0,G1) has girth 5, regularity 36 and order 2(312−1) =1920.Block deletion provides n(35,5) ≤1860 and n(34,5) ≤1800. •For q=37: Consider the graphs G0=S36(8,14;1,−1,11) and G1=S36(2,4;3,−7,15) defined on the cyclic group (Z36,+). Both graphs are 5-regular, have girth five and disjoint Cayley colors, concretely ±{1,8,11,14}and ±{2,3,4,7,15}, respectively. Hence, the 42-regular graph L37(G0,G1) has girth 5 and order 2736. Deletion provides n(41,5) ≤2664, n(40,5) ≤2592, n(39,5) ≤2520, n(38,5) ≤2448. •For q=41: The (6,5)-cage is unique and it is well known (see [23]) that it can be constructed by removing the vertices of a Petersen graph from the Hoffman–Singleton cage. We present a construction of the (6,5)-cage as the graph S40(8,16;1,−1,5,−13). We denote it by G0. Due to the uniqueness of this cage, we construct a suitable graph G1according to the following relabeling of the vertices. G0↔G1G0↔G1G0↔G1G0↔G1G0↔G1G0↔G1G0↔G1G0↔G1 0↔0 1 ↔12 2 ↔1 3 ↔20 4 ↔2 5 ↔33 6 ↔3 7 ↔37 8↔7 9 ↔38 10 ↔8 11 ↔18 12 ↔9 13 ↔32 14 ↔10 15 ↔25 16 ↔14 17 ↔5 18 ↔15 19 ↔13 20 ↔16 21 ↔36 22 ↔17 23 ↔27 24 ↔21 25 ↔19 26 ↔22 27 ↔11 28 ↔23 29 ↔35 30 ↔24 31 ↔39 32 ↔28 33 ↔26 34 ↔29 35 ↔4 36 ↔30 37 ↔34 38 ↔31 39 ↔6 Since G0and G1have no Cayley color in common, the 47-regular graph L41(G0,G1) has girth 5 and order 2(412−1) =3360. Deletion and inequality (2) provide entries k=43,44,45,46 of Table 2. 1886 •For q=43,47: Since we resort to 5-regularity, there exist several pairs of suitable graphs. For the sake of uniformity, we consider the graphs Sq−1(6,12;1,−1,9) and Sq−1(2,4;3,−7,15). It proves that n(48,5) ≤2(432−1) =3696 and n(52,5) ≤ 2(472−1) =4416. As a curiosity, let us mention that the graph S42(1,−1,−7,11,15) is the (5,6)-cage and it forms a suitable pair with S42(2,4;5,−5,17). Based on the above constructions and recalling that it is possible to delete blocks of points and lines we can write the following theorem. Theorem 4.1. The following upper bound on the order of a k-regular graph of girth 5holds k rec(k,5) 32,33 56(k−3) 34,35,36 60(k−4) 38, . . . , 42 72(k−4) 43, . . . , 47 80(k-5) 48 3696 49, . . . , 52 92(k−4) To finalize this section we prove Theorem 1.1. In this case we generate a pair of 6-regular suitable graphs to be amalgamated into Lq, for an odd prime power q≥49. We start with q=49; notice that this case is sharp because the Hoffman–Singleton graph is the Moore cage that attains the lower bound n0(7,5) =50 (see [19]). Theorem 1.1. Given an integer k ≥53, let q be the lowest odd prime power, such that k ≤q+6. Then n(k,5) ≤2(q−1)(k−5). Proof. First consider q=49. Add to the 4-regular bipartite graph S48(1,−1,5,−13) the edges {2v, 2v+8}over the even vertices of Z48, and the four cycles {1+i,17 +i,41 +i,25 +i,9+i,33 +i,1+i}, for i=0,2,4,6, over the odd vertices. We call this (6,5)-graph G0.To construct a suitable graph G1, we resort to the following relabeling of the vertices G0↔G1G0↔G1G0↔G1G0↔G1G0↔G1G0↔G1G0↔G1G0↔G1 0↔0 1 ↔42 2 ↔1 3 ↔39 4 ↔2 5 ↔23 6 ↔3 7 ↔47 8↔6 9 ↔4 10 ↔7 11 ↔28 12 ↔8 13 ↔34 14 ↔9 15 ↔43 16 ↔12 17 ↔35 18 ↔13 19 ↔36 20 ↔14 21 ↔29 22 ↔15 23 ↔44 24 ↔18 25 ↔37 26 ↔19 27 ↔5 28 ↔20 29 ↔40 30 ↔21 31 ↔10 32 ↔24 33 ↔45 34 ↔25 35 ↔46 36 ↔26 37 ↔38 38 ↔27 39 ↔16 40 ↔30 41 ↔41 42 ↔31 43 ↔17 44 ↔32 45 ↔11 46 ↔33 47 ↔22 The graphs G0and G1have disjoint Cayley colors, namely w(G0)= ±{1,5,8,13,16,24}and w(G1)=Z48 −(w(G0)∪{0}). Hence, G0and G1is a suitable pair of graphs to be amalgamated into L49.Using these graphs and also the fact that we can delete blocks of points and lines we prove the theorem for 53 ≤k≤55. When q∈ {53,67,71,79, . . .}is an odd prime power, we consider the 6-regular graphs G0=Sq−1(8,16;1,−1,5,−13) and G1=Sq−1(2,4;3,−7,15,−21). Direct checking shows their suitability over Lqfor q=53,67,71. When q≥ 79, the suitability of G0and G1is a consequence of Lemma 4.3, because the infinite graphs S∞(8,16;1,−1,5,−13) and S∞(2,4;3,−7,15,−21) have girth 5 and spans 32 and 37, respectively. When q∈ {59,61,73}, the graph G0= Sq−1(8,16;1,−1,5,−13) and G1=Sq−1(2,4;3,−7,15, α), where α= −23 for q=59,73 and α= −25 for q=61, is a suitable pair of graphs over Lq.Therefore, for q≥49, the (q+6)-regular graph Lq(G0,G1) has girth at least 5 and order 2(q2−1). Also, according to inequality (2),n(k,5) ≤2(q−1)(k−5), for regularities 56 ≤k≤q+6.■ Remark 4.1. Notice that Theorem 1.1 improves Jørgensen’s result n(q+⌊√q−1 4⌋,5) ≤2(q2−1) (see [20]) for q≤571 and ties with it for 578 ≤k≤779. 5. General constructions for q=2m In this last section we amalgamate into Cqfor q=2mwhen m≥5 applying Theorem 3.1 on regular graphs. The case m=4 was considered in Section 3, where we amalgamated bi-regular graphs. First, we deal with m=5 or q=32. Since an r-regular graph with 32 vertices and girth 5 can reach at most 5-regularity, we have the following sharp result. Theorem 5.1. There exists a 37-regular graph with girth 5and order 2048. Proof. As in the case q=16, denote the elements of (F32,+)∼ =((Z2)5,+) by defgh instead of {d,e,f,g,h}. Let G0be the (5,5)-graph with order 32 and with the following adjacency list: