×

On the girth of extremal graphs without shortest cycles. (English) Zbl 1158.05031

Summary: Let \(EX(\nu ;\{C_{3},\ldots ,C_n\})\) denote the set of graphs \(G\) of order \(\nu \) that contain no cycles of length less than or equal to \(n\) which have maximum number of edges. In this paper we consider a problem posed by several authors: does \(G\) contain an \(n+1\) cycle? We prove that the diameter of \(G\) is at most \(n - 1\), and present several results concerning the above question: the girth of \(G\) is \(g=n+1\) if (i) \(\nu \geq n+5\), diameter equal to \(n - 1\) and minimum degree at least 3; (ii) \(\nu \geq 12, \nu \notin\{15,80,170\}\) and \(n=6\). Moreover, if \(\nu =15\) we find an extremal graph of girth 8 obtained from a 3-regular complete bipartite graph subdividing its edges. (iii) We prove that if \(\nu \geq 2n - 3\) and \(n\geq 7\) the girth is at most \(2n - 5\). We also show that the answer to the question is negative for \(\nu \leq n+1+\lfloor (n - 2)/2\rfloor \).

MSC:

05C35 Extremal problems in graph theory
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Abajo, A. Diánez, Extremal graphs with fixed excess (submitted for publication); E. Abajo, A. Diánez, Extremal graphs with fixed excess (submitted for publication)
[2] 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
[3] Balbuena, C.; García-Vázquez, P.; Marcote, X.; Valenzuela, J. C., Extremal bipartite graphs with high girth, Ars Combin., 83, 3-14 (2007) · Zbl 1174.05064
[4] Chartrand, G.; Lesniak, L., Graphs and Digraphs (1996), Chapman and Hall: Chapman and Hall London, UK · Zbl 0890.05001
[5] Erdös, P.; Sachs, H., Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Uni. Halle (Math. Nat.), 12, 251-257 (1963) · Zbl 0116.15002
[6] Fàbrega, J.; Fiol, M. A., Maximally connected digraphs, J. Graph Theory, 13, 3, 657-668 (1989) · Zbl 0688.05029
[7] Fiol, M. A.; Fàbrega, J.; Escudero, M., Short paths and connectivity in graphs and digraphs, Ars Combin., 29B, 17-31 (1990) · Zbl 0708.05025
[8] 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
[9] Garnick, D. K.; Nieuwejaar, N. A., Non-isomorphic extremal graphs without three-cycles or four-cycles, JCMCC, 12, 33-56 (1992) · Zbl 0773.05064
[10] Godsil, C.; Royle, G., Algebraic Graph Theory (2001), Springer-Verlag Inc.: Springer-Verlag Inc. New York · Zbl 0968.05002
[11] Imase, M.; Soneoka, T.; Okada, K., Connectivity of regular directed graphs with small diameter, IEEE Trans. Comput., C-34, 267-273 (1985) · Zbl 0554.05044
[12] Lovász, L., Combinatorial Problems and Exercises (1979), North-Holland: North-Holland Amsterdam · Zbl 0439.05001
[13] Lazebnik, F.; Wang, Ping, On the structure of extremal graphs of high girth, J. Graph Theory, 26, 147-153 (1997) · Zbl 0883.05077
[14] J. Tang, Y. Lin, C. Balbuena, M. Miller, Calculating the extremal number \(e x ( v ; \{ C_3 , C_4 , \ldots , C_n \} )\), Discrete Appl. Math. (2007) (in press); J. Tang, Y. Lin, C. Balbuena, M. Miller, Calculating the extremal number \(e x ( v ; \{ C_3 , C_4 , \ldots , C_n \} )\), Discrete Appl. Math. (2007) (in press) · Zbl 1184.05069
[15] Wong, P. K., Cages-A survey, J. Graph Theory, 6, 1-22 (1982) · 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.