Debido a tareas de mantenimiento del servidor los perfiles de autor no están disponibles, rogamos disculpen las molestias. Due to server maintenance, author profiles are not available. We apologize for the inconvenience.
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/ | |