Artículo
On the girth of extremal graphs without shortest cycles
Autor/es | Balbuena, C.
Cera López, Martín Diánez Martínez, Ana Rosa García Vázquez, Pedro |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2008 |
Fecha de depósito | 2024-10-16 |
Publicado en |
|
Resumen | Let E X(ν;{C3, . . . ,Cn}) denote the set of graphs G of order ν 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: ... Let E X(ν;{C3, . . . ,Cn}) denote the set of graphs G of order ν 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) ν ≥ n + 5, diameter equal to n − 1 and minimum degree at least 3; (ii) ν ≥ 12, ν 6∈ {15, 80, 170} and n = 6. Moreover, if ν = 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 ν ≥ 2n − 3 and n ≥ 7 the girth is at most 2n − 5. We also show that the answer to the question is negative for ν ≤ n + 1 + b(n − 2)/2c. |
Cita | Balbuena, C., Cera López, M., Diánez Martínez, A.R. y García Vázquez, P. (2008). On the girth of extremal graphs without shortest cycles. Discrete Mathematics, 308 (23), 5682-5690. https://doi.org/10.1016/j.disc.2007.10.037. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
On the girth...pdf | 372.5Kb | [PDF] | Ver/ | |