New family of small regular graphs of girth 5

New family of small regular graphs of girth 5 E. Abajo 1,2 Departamento Matem´atica Aplicada I Univ. de Sevilla Sevilla, Spain G. Araujo-Pardo 3 Instituto de Matem´aticas Univ. Nacional Aut´onoma de M´exico Ciudad de M´exico, M´exico C. Balbuena 4 Departament d’Enginyeria Civil i Ambiental Univ. Polit`ecnica de Catalunya Barcelona, Spain M. Bendala 5 Departamento Matem´atica Aplicada I Univ. de Sevilla Sevilla, Spain Abstract A(k, g)-cage is a k-regular graph of girth g of minimum order. In this work, we focus on girth g = 5, where cages are known only for degrees k ≤ 7. When k ≥ 8, except perhaps for k =57, the order of a (k, 5)-cage is strictly greater http://dx.doi.org/10.1016/j.endm.2016.09.025 1571-0653/ than 1 + k2.Considering the relationship between finite geometries and graphs we establish upper constructive bounds that improve the best so far. Keywords: Regular graph, cage, girth, amalgam. 1 Introduction and Results All the graphs considered are finite and simple. Let Gbe a graph with vertex set Vand edge set E.Thegirth of a graph Gis the length 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,k 2)-regular if all its vertices have either degree k1or k2.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 order of a (k, g)-cage is denoted by n(k, g). Cages were introduced by Tutte [15] in 1947 and their existence was proved by Erd˝os and Sachs [6] 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 with respect either a vertex (for odd g), or and 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)ifgis even. Obviously a graph that attains this lower bound is a (k, g)-cage. There has been intense work related with The Cage Problem, focussed on constructing smallest (k, g)-graphs (for a complete survey of this topic see [8]). In particular, we are interested in the cage problem for g=5. Inthis case n0(k, 5) = 1 + k2and it is well known that this bound is attained for k=2,3,7 and perhaps for k=57(see[4]). For k=4,5,6, the known graphs of minimum order are cages (see [11,12,16]). 1Research supported by the Ministry of Education and Science, Spain, the European Regional Development Fund (ERDF) under project MTM2014-60127-P, CONACyT-M´exico under projects 57371, 166306, and PAPIIT-M´exico under project IN104915. 2Email: [email protected] 3Email: [email protected] 4Email: [email protected] 5Email: [email protected] E. Abajo et al. / Electronic Notes in Discrete Mathematics 54 (2016) 139–144140 Jørgensen [10] establishes that, for every odd prime power q≥13 and k≤q+3,n(k, 5) ≤2(q−1)(k−2). Abreu et al. [1] prove that for any prime q≥13 and k≤q+3,n(k, 5) ≤2(qk −3q−1) improving the Jørgensen’s bound except for k=q+ 3 where the bounds coincide. In [9] 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 in the (bipartite) incidence graph, also called Levi Graph of elliptic semiplanes of type C and L (see [3,5,9]). We improve some results of Funk finding the best possible regular graphs to amalgamate which allows us to obtain new better upper bounds. Our techniques are a refinement to those used in [1]and[2], where the authors not only amalgamate regular graphs, but also bi-regular graphs. In this way, (k, 5)-graphs are constructed for 17 ≤k≤22 using the incidence graphs of elliptic semi planes 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 [8,9], 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). krec(k,5) Due to Reference New rec(k,5) 880 Jørgensen, Royle [10], [13] 996 Jørgensen [10] 10 124 Exoo [7] 11 154 Exoo [7] 12 203 Exoo [7] 13 230 Exoo [7] 14 284 Abreu et al. [1] 15 310 Abreu et al. [1] 16 336 Jørgensen [10] 17 448 Schwenk [14]436 18 480 Schwenk [14]468 19 512 Schwenk [14]500 20 572 Abreu et al. [1]564 21 682 Abreu et al. [1]666 22 720 Jørgensen [10]704 Table 1 Current upper bounds and our new bounds on n(k, 5) for 8 ≤k≤22. E. Abajo et al. / Electronic Notes in Discrete Mathematics 54 (2016) 139–144 141 The bounds obtained by Funk using elliptic semiplanes of type L on n(k, 5) for 23 ≤k≤31 remain untouched whereas, for 32 ≤k≤52, we obtain the best possible graphs to amalgamate in this type of incidence graphs obtaining, in consequence, the best upper bounds known hitherto for these values (see Table 2). krec(k,5) Due to Reference New rec(k,5) 32 1680 Jørgensen [10]1624 33 1856 Funk [9]1680 34 1920 Jørgensen [10]1800 35 1984 Funk [9]1860 36 2048 Funk [9]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 [10]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 [10]3120 45 3610 Abreu et al [1]3200 46 3696 Jørgensen [10]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 [10]4232 51 4704 Jørgensen [10]4324 52 4800 Jørgensen [10]4416 Table 2 Current upper bounds and our new bounds on n(k, 5) for 32 ≤k≤52. Finally, when q>49 is a prime power, the construction of a suitable 6-regular pair of graphs has allowed us to establish the following general results. Note that the bounds are different depending on the parity of q. Theorem 1.1 Let k≥53 be an integer and qthe smallest odd prime power with k≤q+6.Thenn(k, 5) ≤2(q−1)(k−5). Theorem 1.2 Let k≥68 be an integer and qthe smallest even prime power such that k≤q+6.Thenn(k, 5) ≤2q(k−6). E. Abajo et al. / Electronic Notes in Discrete Mathematics 54 (2016) 139–144142 To point out that the above theorems represent a considerable improvement to the current known bounds, we show explicitly the next two bounds. krec(k,5) Due to Reference New rec(k,5) 55 5510 Abreu et al [1]4800 70 8976 Jørgensen [10]8192 We want to emphasize that all the bounds on n(k, 5) contained in this paper are obtained constructively, that is, we construct a (k, 5)-graph with order rec(k, 5). 2 Bibliographical references References [1] Abreu, M., G. Araujo-Pardo, C. Balbuena and D. Labbate, Families of small regular graphs of girth 5, Discrete Math. 312 (2012), 2832 – 2842. [2] Abreu, M., G. Araujo-Pardo, C. Balbuena, G. L´opez-Ch´avez and D. Labbate, Biregular cages of girth 5, Electronic Journal of Combinatorics 20 (2013), Issue 1, # P71. [3] Abreu, M., M. Funk, D. Labbate and V. Napolitano, A(0,1)–matrix framework for elliptic semiplanes, Ars Combinatoria 88 (2008), 175–191. [4] Biggs, N., “Algebraic Graph Theory,” Cambridge University Press, New York, 1996. [5] Dembowski, P., “Finite Geometries,” Springer, New York 1968, reprint 1997. [6] Erd¨os, P. and H. Sachs, Regul¨are Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Uni. Halle (Math. Nat.) 12 (1963), 251–257. [7] Exoo, G., Regular graphs of given degree and girth,URL: http://ginger.indstate.edu/ge/CAGES. [8] Exoo, G. and R. Jajcay, Dynamic Cage Survey, The Electronic Journal of Combinatorics (2008), # DS 16, URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS16/pdf. E. Abajo et al. / Electronic Notes in Discrete Mathematics 54 (2016) 139–144 143 [9] Funk, M., Girth 5graphs from elliptic semiplanes, Note di Matematica 29 (2009), suppl.1, 91 – 114. [10] Jørgensen, L.K., Girth 5graphs from relative difference sets, Discrete Math. 293 (2005), 177 – 184. [11] O’Keefe, M. and P.K. Wong, A smallest graph of girth 5and valency 6, J. Combin. Theory 26 (1979), Ser. B, 145 – 149. [12] Robertson, N., The smallest graph of girth 5and valency 4, Bull. Amer. Math. Soc. 70 (1964), 824 – 825. [13] Royle, G., Cages of Higher Valency,URL: http://school.maths.uwa.edu.au/ gordon/remote/cages/allcages.html. [14] Schwenk, A., Construction of a small regular graph of girth 5and degree 19, Conference Presentation given at Normal, II, USA, (18. April 2008). [15] Tutte, W. T., A family of cubical graphs, Proc. Cambridge Philos. Soc. (1947), 459–474. [16] Wegner, G., A smallest graph of girth 5and valency 5, J. Combin. Theory 14 (1973), Ser. B, 203–208. E. Abajo et al. / Electronic Notes in Discrete Mathematics 54 (2016) 139–144144