Article
On the Minimum Order of Extremal Graphs to have a Prescribed Girth
Author/s | Balbuena, C.
García Vázquez, Pedro |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Publication Date | 2007 |
Deposit Date | 2017-04-05 |
Published in |
|
Abstract | We show that any n‐vertex extremal graph G without cycles of length at most k has girth exactly $k+1$ if $k\ge 6$ and $n>(2(k-2)^{k-2}+k-5)/(k-3)$. This result provides an improvement of the asymptotical known result by ... We show that any n‐vertex extremal graph G without cycles of length at most k has girth exactly $k+1$ if $k\ge 6$ and $n>(2(k-2)^{k-2}+k-5)/(k-3)$. This result provides an improvement of the asymptotical known result by Lazebnik and Wang [J. Graph Theory, 26 (1997), pp. 147–153] who proved that the girth is exactly $k+1$ if $k\ge 12$ and $n\ge 2^{a^2+a+1}k^a$, where $a=k-3-\lfloor(k-2)/4\rfloor$. Moreover, we prove that the girth of G is at most $k+2$ if $n>(2(t-2)^{k-2}+t-5)/(t-3)$, where $t=\lceil (k+1)/2\rceil\ge 4$. In general, for $k\ge 5$ we show that the girth of G is at most $2k-4$ if $n\ge 2k-2$. |
Citation | Balbuena, C. y García Vázquez, P. (2007). On the Minimum Order of Extremal Graphs to have a Prescribed Girth. SIAM Journal on Discrete Mathematics, 21 (1), 251-257. |
Files | Size | Format | View | Description |
---|---|---|---|---|
060656747.pdf | 120.4Kb | [PDF] | View/ | |