An alternate description of a \((q + 1, 8)\)-cage. (English) Zbl 1421.05070
Summary: Let \(q \geq 2\) be a prime power. In this note we present an alternate description of the known \((q + 1, 8)\)-cages which has allowed us to construct small \((k, g)\)-graphs for \(k = q - 1, q\) and \(g = 7, 8\) in other papers on this same topic.
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C35 | Extremal problems in graph theory |
| 05B25 | Combinatorial aspects of finite geometries |
Software:
GENREGReferences:
| [1] | M. Abreu, G. Araujo-Pardo, C. Balbuena and D. Labbate, Families of small regular graphs of girth 5, Discrete Math. 312 (2012), 2832-2842, doi:10.1016/j.disc.2012.05.020. · Zbl 1248.05169 |
| [2] | M. Abreu, G. Araujo-Pardo, C. Balbuena and D. Labbate, A construction of small (q − 1)regular graphs of girth 8, Electron. J. Combin. 22 (2015), #P2.10 (8 pages),https://www. combinatorics.org/ojs/index.php/eljc/article/view/v22i2p10. · Zbl 1310.05152 |
| [3] | M. Abreu, G. Araujo-Pardo, C. Balbuena, D. Labbate and J. Salas, Families of small regular graphs of girth 7, Electron. Notes Discrete Math. 40 (2013), 341-345, doi:10.1016/j.endm. 2013.05.060. · Zbl 1327.05163 |
| [4] | M. Abreu, G. Araujo-Pardo, C. Balbuena, D. Labbate and J. Salas, Small regular graphs of girth 7, Electron. J. Combin. 22 (2015), #P3.5 (16 pages),https://www.combinatorics. org/ojs/index.php/eljc/article/view/v22i3p5. · Zbl 1327.05163 |
| [5] | M. Abreu, M. Funk, D. Labbate and V. Napolitano, On (minimal) regular graphs of girth 6, Australas. J. Combin.35 (2006), 119-132,https://ajc.maths.uq.edu.au/pdf/35/ ajc_v35_p119.pdf. · Zbl 1102.05034 |
| [6] | M. Abreu, M. Funk, D. Labbate and V. Napolitano, A family of regular graphs of girth 5, Discrete Math.308 (2008), 1810-1815, doi:10.1016/j.disc.2007.04.031. · Zbl 1151.05021 |
| [7] | G. Araujo-Pardo, C. Balbuena and T. H´eger, Finding small regular graphs of girths 6, 8 and 12 as subgraphs of cages, Discrete Math. 310 (2010), 1301-1306, doi:10.1016/j.disc.2009.12.014. · Zbl 1205.05064 |
| [8] | C. Balbuena, Incidence matrices of projective planes and of some regular bipartite graphs of girth 6 with few vertices, SIAM J. Discrete Math. 22 (2008), 1351-1363, doi:10.1137/ 070688225. · Zbl 1229.05130 |
| [9] | C. Balbuena, A construction of small regular bipartite graphs of girth 8, Discrete Math. Theor. Comput. Sci.11 (2009), 33-46,https://dmtcs.episciences.org/461. · Zbl 1196.05025 |
| [10] | E. Bannai and T. Ito, On finite Moore graphs, J. Fac. Sci. Univ. Tokyo Sect. IA Math. 20 (1973), 191-208,http://hdl.handle.net/2261/6123. · Zbl 0275.05121 |
| [11] | L. M. Batten, Combinatorics of Finite Geometries, Cambridge University Press, Cambridge, 2nd edition, 1997, doi:10.1017/cbo9780511665608. · Zbl 0885.51012 |
| [12] | C. T. Benson, Minimal regular graphs of girths eight and twelve, Canadian J. Math. 18 (1966), 1091-1094, doi:10.4153/cjm-1966-109-8. · Zbl 0146.45701 |
| [13] | N. Biggs, Algebraic Graph Theory, volume 67 of Cambridge Mathematical Library, Cambridge University Press, Cambridge, 2nd edition, 1993, doi:10.1017/cbo9780511608704. · Zbl 0797.05032 |
| [14] | J. A. Bondy and U. S. R. Murty, Graph Theory, volume 244 of Graduate Texts in Mathematics, Springer, New York, 2008, doi:10.1007/978-1-84628-970-5. · Zbl 1134.05001 |
| [15] | P. Erd˝os and H. Sachs, Regul¨are Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 12 (1963), 251-257, https://users.renyi.hu/˜p_erdos/1963-16.pdf. · Zbl 0116.15002 |
| [16] | G. Exoo, A simple method for constructing small cubic graphs of girths 14, 15, and 16, Electron. J. Combin.3 (1996), #R30 (3 pages),https://www.combinatorics.org/ojs/ index.php/eljc/article/view/v3i1r30. · Zbl 0885.05057 |
| [17] | G. Exoo and R. Jajcay, Dynamic cage survey, Electron. J. Combin. (2013), #DS16 (55 pages),https://www.combinatorics.org/ojs/index.php/eljc/article/ view/DS16. · Zbl 1169.05336 |
| [18] | A. G´acs and T. H´eger, On geometric constructions of (k, g)-graphs, Contrib. Discrete Math. 3 (2008), 63-80, doi:10.11575/cdm.v3i1.61998. · Zbl 1203.05076 |
| [19] | C. Godsil and G. Royle, Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics, Springer-Verlag, New York, 2001, doi:10.1007/978-1-4613-0163-9. · Zbl 0968.05002 |
| [20] | F. Lazebnik, V. A. Ustimenko and A. J. Woldar, New upper bounds on the order of cages, Electron. J. Combin.4 (1997), #R13 (11 pages),https://www.combinatorics.org/ ojs/index.php/eljc/article/view/v4i2r13. · Zbl 0885.05078 |
| [21] | M. Meringer, Fast generation of regular graphs and construction of cages, J. Graph Theory 30 (1999), 137-146, doi:10.1002/(sici)1097-0118(199902)30:2h137::aid-jgt7i3.0.co;2-g. · Zbl 0918.05062 |
| [22] | M. O’Keefe and P. K. Wong, The smallest graph of girth 6 and valency 7, J. Graph Theory 5 (1981), 79-85, doi:10.1002/jgt.3190050105. · Zbl 0448.05041 |
| [23] | S. E. Payne, Affine representations of generalized quadrangles, J. Algebra 16 (1970), 473-485, doi:10.1016/0021-8693(70)90001-3. · Zbl 0207.19402 |
| [24] | S. E. Payne and J. A. Thas, Finite Generalized Quadrangles, volume 110 of Research Notes in Mathematics, Pitman Advanced Publishing Program, Boston, MA, 1984. · Zbl 0551.05027 |
| [25] | W. T. Tutte, A family of cubical graphs, Proc. Cambridge Philos. Soc. 43 (1947), 459-474, doi:10.1017/s0305004100023720. · Zbl 0029.42401 |
| [26] | V. A. Ustimenko, A linear interpretation of the flag geometries of Chevalley groups, Ukr. Math. J.42 (1990), 341-344, doi:10.1007/bf01057020. · Zbl 0704.51004 |
| [27] | J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press, Cambridge, 1992. · Zbl 0769.05001 |
| [28] | H. van Maldeghem, Generalized Polygons, volume 93 of Monographs in Mathematics, Birkh¨auser Verlag, Basel, 1998, doi:10.1007/978-3-0348-0271-0. · Zbl 0914.51005 |
| [29] | P. K. Wong, Cages—a survey, J. Graph Theory 6 (1982), 1-22, doi:10.1002/jgt.3190060103. · Zbl 0488.05044 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
