×

zbMATH — the first resource for mathematics

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:
GENREG
PDF BibTeX XML Cite
Full Text: DOI
References:
[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. 8Art Discrete Appl. Math. 1 (2018) #P2.07 · 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.
[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.
[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.
[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.
[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.
[25] W. T. Tutte, A family of cubical graphs, Proc. Cambridge Philos. Soc. 43 (1947), 459-474, doi:10.1017/s0305004100023720. M. Abreuet al.: An alternate description of a (q + 1, 8)-cage9 · 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.
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.