×

New families of graphs without short cycles and large size. (English) Zbl 1230.05170

Summary: We denote by \(ex(n;\{ C_{3},C_{4},\ldots ,Cs \} )\) or \(f_s(n)\) the maximum number of edges in a graph of order \(n\) and girth at least \(s+1\). First we give a method to transform an \(n\)-vertex graph of girth \(g\) into a graph of girth at least \(g - 1\) on fewer vertices. For an infinite sequence of values of \(n\) and \(s \in \{ 4,6,10 \}\) the obtained graphs are denser than the known constructions of graphs of the same girth \(s+1\). We also give another different construction of dense graphs for an infinite sequence of values of \(n\) and \(s \in \{ 7,11 \}\). These two methods improve the known lower bounds on \(f_s(n)\) for \(s \in \{ 4,6,7,10,11 \}\) which were obtained using different algorithms. Finally, to know how good are our results, we have proved that \(\lim \sup _{n \to \infty} \frac{f_s(n)}{n^{1+ \frac {2}{s-1}}} = 2^{-1- \frac{2}{s-1}}\) for \(s \in \{ 5,7,11 \}\), and \(s^{-1- \frac 2s} \leq \lim \sup _{n \to \infty} \frac{f_s(n)}{n^{1+ \frac 2s}} \leq 0.5\) for \(s \in \{ 6,10 \}\).

MSC:

05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Abajo, A. Diánez, Exact values of \(\operatorname{ex} ( n ; \{ C_3 , C_4 , \ldots , C_s \} )\); E. Abajo, A. Diánez, Exact values of \(\operatorname{ex} ( n ; \{ C_3 , C_4 , \ldots , C_s \} )\)
[2] E. Abajo, A. Diánez, Extremal graphs as sparse graphs, preprint.; E. Abajo, A. Diánez, Extremal graphs as sparse graphs, preprint.
[3] Alon, N.; Hoory, S.; Linial, N., The Moore bound for irregular graphs, Graphs Combin., 18, 53-57 (2002) · Zbl 0990.05075
[4] Araujo-Pardo, G.; Balbuena, C.; Valenzuela, J. C., Constructions of bi-regular cages, Discrete Math., 309, 6, 1409-1416 (2009) · Zbl 1229.05129
[5] Balbuena, C.; Cera, M.; Diánez, A.; García-Vázquez, P., On the girth of extremal graphs without shortest cycles, Discrete Math., 308, 23, 5682-5690 (2008) · Zbl 1158.05031
[6] Balbuena, C.; García-Vázquez, P., On the minimum order of extremal graphs to have a prescribed girth, SIAM J. Discrete Math., 21, 1, 251-257 (2007) · Zbl 1154.05040
[7] Bannai, E.; Ito, T., On finite Moore graphs, J. Fac. Sci. Tokyo Univ., 20, 191-208 (1973) · Zbl 0275.05121
[8] Benson, C. T., Minimal regular graphs of girth eight and twelve, Canad. J. Math., 18, 1091-1094 (1966) · Zbl 0146.45701
[9] Biggs, N., Algebraic Graph Theory (1996), Cambridge University Press: Cambridge University Press New York
[10] Biggs, N., Construction for cubic graphs with large girth, Electron. J. Combin., 5, #A1 (1998) · Zbl 0911.05036
[11] Buekenhout, F., Handbook of Incidence Geometry (1995), Elsevier Science · Zbl 0821.00012
[12] Chartrand, G.; Lesniak, L., Graphs and Digraphs (1996), Chapman and Hall: Chapman and Hall London, UK · Zbl 0890.05001
[13] Damerell, R. M., On Moore graphs, Proc. Cambridge Philos. Soc., 74, 227-236 (1973) · Zbl 0262.05132
[14] Erdös, P., Some recent progress on extremal problems in graph theory, Congr. Numer., 14, 3-4 (1975)
[15] Feit, W.; Higman, G., The non-existence of certain generalized polygons, J. Algebra, 1, 114-131 (1964) · Zbl 0126.05303
[16] Garnick, D. K.; Kwong, Y. H.H.; Lazebnik, F., Extremal graphs without three-cycles or four-cycles, J. Graph Theory, 17, 633-645 (1993) · Zbl 0784.05033
[17] Garnick, D. K.; Nieuwejaar, N. A., Non-isomorphic extremal graphs without three-cycles or four-cycles, J. Combin. Math. Combin. Comput., 12, 33-56 (1992) · Zbl 0773.05064
[18] Hoffman, A. J.; Singleton, R. R., On Moore graphs with diameter 2 and 3, IBM J. Res. Dev., 4, 497-504 (1960) · Zbl 0096.38102
[19] Holton, D. A.; Sheehan, J., The Petersen Graph (1993), Cambridge University: Cambridge University Cages, (Chapter 6) · Zbl 0781.05001
[20] Lazebnik, F.; Ustimenko, V. A.; Woldar, A. J., A new series of dense graphs of high girth, Bull. Amer. Math. Soc. (N.S.), 32, 1, 73-79 (1995) · Zbl 0822.05039
[21] Simonovits, M., (Beineke, L. W.; Wilson, R. J., Extremal Graph Theory. Extremal Graph Theory, Selected Topics in Graph Theory, vol. 2 (1983), Academic Press: Academic Press London), 161-200 · Zbl 0531.05037
[22] Tang, J.; Lin, Y.; Balbuena, C.; Miller, M., Calculating the extremal number \(ex(n; \{C_3, C_4, \ldots, C_s \})\), Discrete Appl. Math., 157, 9, 2198-2206 (2009) · Zbl 1184.05069
[23] van Lint, J. H.; Wilson, R. M., A Course in Combinatorics (1994), Cambridge University Press: Cambridge University Press UK · Zbl 0769.05001
[24] Wang, P.; Dueck, G. W.; MacMillan, S., Using simulated annealing to construct extremal graphs, Discrete Math., 235, 125-135 (2001) · Zbl 0977.05131
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.