×

zbMATH — the first resource for mathematics

New small regular graphs of girth 5. (English) Zbl 1362.05064
Summary: A \((k, g)\)-graph is a \(k\)-regular graph with girth \(g\) and 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 \leq 7\). We construct \((k, 5)\)-graphs using techniques exposed by M. Funk [Note Mat. 29, Suppl. 1, 93–117 (2009; Zbl 1248.05089)] and M. Abreu et al. [Discrete Math. 312, No. 18, 2832–2842 (2012; Zbl 1248.05169)] 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.

MSC:
05C35 Extremal problems in graph theory
05C38 Paths and cycles
05C75 Structural characterization of families of graphs
Software:
GENREG
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abreu, M.; Araujo-Pardo, G.; Balbuena, C.; Labbate, D., Families of small regular graphs of girth \(5\), Discrete Math., 312, 2832, (2012) · Zbl 1248.05169
[2] Abreu, M.; Araujo-Pardo, G.; Balbuena, C.; López-Chávez, G.; Labbate, D., Biregular cages of girth \(5\), Electron. J. Combin., 20, 1, #P71, (2013) · Zbl 1266.05072
[3] Abreu, M.; Funk, M.; Labbate, D.; Napolitano, V., On (minimal) regular graphs of girth \(6\), Australas. J. Combin., 35, 119-132, (2006) · Zbl 1102.05034
[4] Abreu, M.; Funk, M.; Labbate, D.; Napolitano, V., A family of regular graphs of girth \(5\), Discrete Math., 308, 10, 1810-1815, (2008) · Zbl 1151.05021
[5] Abreu, M.; Funk, M.; Labbate, D.; Napolitano, V., A \((0, 1)\)-matrix framework for elliptic semiplanes, Ars Combinatoria, 88, 175-191, (2008) · Zbl 1224.51011
[6] Araujo-Pardo, G.; Balbuena, C., Constructions of small regular bipartite graphs of girth 6, Networks, 57, 2, 121-127, (2011) · Zbl 1210.05075
[7] Araujo-Pardo, G.; Balbuena, C.; Héger, T., Finding small regular graphs of girth \(6\), \(8\) and \(12\) as subgraphs of cages, Discrete Math., 310, 1301-1306, (2010) · Zbl 1205.05064
[8] Araujo-Pardo, G.; González-Moreno, D.; Montellano, J. J.; Serra, O., On upper bounds and conectivity of cages, Australas J. Combin., 38, 221-228, (2007)
[9] Balbuena, C., Incidence matrices of projective planes and of some regular bipartite graphs of girth 6 with few vertices, SIAM J. Discrete Math., 22, 4, 131-1363, (2008) · Zbl 1229.05130
[10] Balbuena, C.; Miller, M.; Širáň, J.; Ždímalová, M., Large-vertex transitive graphs of diameter 2 from incidence graphs of biaffine planes, Discrete Math., 313, 199, 2014-2019, (2013) · Zbl 1277.05049
[11] Biggs, N., Algebraic Graph Theory, (1996), Cambridge University Press New York
[12] Coxeter, H. S.M., Self-dual configurations and regular graphs, Bull. Amer. Math. Soc. (N.S.), 56, 413-455, (1950) · Zbl 0040.22803
[13] Dembowski, P., Finite Geometries, (1968), Springer New York, reprint 1997 · Zbl 0159.50001
[14] Erdös, P.; H., Sachs, Reguläre graphen gegebener taillenweite mit minimaler knotenzahl, Wiss. Z. Uni. Halle (Math. Nat.), 12, 251-257, (1963) · Zbl 0116.15002
[15] G. Exoo, Regular graphs of given degree and girth, (http://ginger.indstate.edu/ge/CAGES) · Zbl 1246.05070
[16] Exoo, G.; Jajcay, R., Dynamic cage survey, Electron. J. Combin., 15, # DS 16, (2008), (http://www.combinatorics.org/Surveys/ds16.pdf)
[17] Funk, M., Girth \(5\) graphs from elliptic semiplanes, Note di Matematica, 29, suppl.1, 91-114, (2009) · Zbl 1248.05089
[18] Hafner, P., Geometric realisation of the graphs of mckay-Miller-širáň, J. Combin. Theory Ser. B, 90, 223-232, (2004) · Zbl 1043.05060
[19] Hoffman, A. J.; Singleton, R. R., On Moore graphs with diameters 2 and 3, IBM J., November, 497-504, (1960) · Zbl 0096.38102
[20] Jørgensen, L. K., Girth \(5\) graphs from relative difference sets, Discrete Math., 293, 177-184, (2005) · Zbl 1062.05069
[21] Lazebnik, F.; Ustimenko, V. A., Explicit construction of graphs with an arbitrary large girth and of large size, Discrete Appl. Math., 60, 275-284, (1995) · Zbl 0840.05045
[22] Meringer, M., Fast generation of regular graphs and construction of cages, J. Graph Theory, 30, 137-146, (1999) · Zbl 0918.05062
[23] O’Keefe, M.; Wong, P. K., A smallest graph of girth \(5\) and valency \(6\), J. Combin. Theory Ser. B, 26, 145-149, (1979) · Zbl 0427.05043
[24] Robertson, N., The smallest graph of girth \(5\) and valency \(4\), Bull. Amer. Math. Soc. (N.S.), 70, 824-825, (1964) · Zbl 0119.38803
[25] Robertson, N., Graphs Minimal under Girth, Valency and Connectivity Constraints, Dissertation, Univ. of Waterloo, (1969)
[26] G. Royle, Cubic Cages (http://people.csse.uwa.edu.au/gordon/cages)
[27] A. Schwenk, Construction of a small regular graph of girth \(5\) and degree \(19\), Conference Presentation given at Normal, II, USA (18 April 2008)
[28] Singer, J., A theorem in projective geometry and some applications to number theory, Trans. Amer. Math. Soc., 43, 377-385, (1938) · JFM 64.0972.04
[29] Tutte, W. T., A family of cubical graphs, Proc. Cambridge Philos. Soc., 459-474, (1947) · Zbl 0029.42401
[30] Wegner, G., A smallest graph of girth \(5\) and valency \(5\), J. Combin. Theory Ser. B, 14, 203-208, (1973) · Zbl 0261.05128
[31] Wong, P. K., On the uniqueness of the smallest graphs of girth \(5\) and valency \(6\), J. Graph Theory, 3, 407-409, (1978) · Zbl 0428.05029
[32] Wong, P. K., Cages-a survey, J. Graph Theory, 6, 1-22, (1982) · Zbl 0488.05044
[33] Yang, Y. S.; Zhang, C. X., A new \((5, 5)\)-cage and the number of \((5, 5)\)-cages (Chinese), J. Math. Res. Exposition, 9, 628-632, (1989) · Zbl 0941.05512
[34] Zitnik, A.; Horvat, B.; Pisanski, T., All generalized Petersen graphs are unit-distance graphs, Institue of Mathematics, Phys. Mech., 48, (2010), 2232-2094
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.