Repositorio de producción científica de la Universidad de Sevilla

On the Minimum Order of Extremal Graphs to have a Prescribed Girth

Opened Access On the Minimum Order of Extremal Graphs to have a Prescribed Girth

Citas

buscar en

Estadísticas
Icon
Exportar a
Autor: Balbuena, C.
García Vázquez, Pedro
Departamento: Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII)
Fecha: 2007
Publicado en: SIAM Journal on Discrete Mathematics, 21 (1), 251-257.
Tipo de documento: Artículo
Resumen: 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$.
Cita: 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.
Tamaño: 120.4Kb
Formato: PDF

URI: http://hdl.handle.net/11441/57152

DOI: 10.1137/060656747

Ver versión del editor

Mostrar el registro completo del ítem


Esta obra está bajo una Licencia Creative Commons An error occurred on the license name.

Este registro aparece en las siguientes colecciones