Artículo
Size of graphs with high girth
Autor/es | Abajo Casado, María Encarnación
Diánez Martínez, Ana Rosa |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2007 |
Fecha de depósito | 2023-10-18 |
Publicado en |
|
Resumen | Let n≥4 be a positive integer and let ex (ν;{C3, . . . , Cn}) denote the maximum number of edges in a {C3, . . . , Cn}-free simple graph of order ν. This paper givesthe exact value of this function for all νup to ⌊(16n−15)/5⌋. ... Let n≥4 be a positive integer and let ex (ν;{C3, . . . , Cn}) denote the maximum number of edges in a {C3, . . . , Cn}-free simple graph of order ν. This paper givesthe exact value of this function for all νup to ⌊(16n−15)/5⌋. This result allows usto deduce all the different values of the girths that such extremal graphs can have. Let k≥0 be an integer. For each n≥2 log2(k+ 2) there exists ν such that every extremal graph Gwith e(G)−ν(G) = khas minimal degree at most 2,and is obtained by adding vertices of degree 1 and/or by subdividing a graph or a multigraph Hwith δ(H)≥3 and e(H)−ν(H) = k. |
Agencias financiadoras | Ministerio de Educación y Ciencia (MEC). España European Commission (EC). Fondo Europeo de Desarrollo Regional (FEDER) |
Identificador del proyecto | MTM2005-08990-C02-02 |
Cita | Abajo Casado, M.E. y Diánez Martínez, A.R. (2007). Size of graphs with high girth. Electronic Notes in Discrete Mathematics, 29, 179-183. https://doi.org/10.1016/j.endm.2007.07.030. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Size of graphs with high girth.pdf | 71.99Kb | [PDF] | Ver/ | |