Mostrar el registro sencillo del ítem
Artículo
On the Minimum Order of Extremal Graphs to have a Prescribed Girth
dc.creator | Balbuena, C. | es |
dc.creator | García Vázquez, Pedro | es |
dc.date.accessioned | 2017-04-05T09:55:00Z | |
dc.date.available | 2017-04-05T09:55:00Z | |
dc.date.issued | 2007 | |
dc.identifier.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. | |
dc.identifier.issn | 0895-4801 | es |
dc.identifier.uri | http://hdl.handle.net/11441/57152 | |
dc.description.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 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$. | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | SIAM | es |
dc.relation.ispartof | SIAM Journal on Discrete Mathematics, 21 (1), 251-257. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | extremal graphs | es |
dc.subject | girth | es |
dc.subject | forbidden cycles | es |
dc.subject | cages | es |
dc.title | On the Minimum Order of Extremal Graphs to have a Prescribed Girth | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) | es |
dc.relation.publisherversion | http://epubs.siam.org/doi/abs/10.1137/060656747 | es |
dc.identifier.doi | 10.1137/060656747 | es |
idus.format.extent | 7 | es |
dc.journaltitle | SIAM Journal on Discrete Mathematics | es |
dc.publication.volumen | 21 | es |
dc.publication.issue | 1 | es |
dc.publication.initialPage | 251 | es |
dc.publication.endPage | 257 | es |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
060656747.pdf | 120.4Kb | [PDF] | Ver/ | |