# Consultar departamento

Por fecha Por autores Por títulos Por temas (CDU)

Del documento Todo RECERCAT

# Mi RECERCAT

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/8745

 Título: New families of graphs without short cycles and large size Abajo, E.; Balbuena Martínez, Maria Camino Teófila; Diánez, A. Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada III; Universitat Politècnica de Catalunya. COMBGRAF - Combinatòria, Teoria de Grafs i Aplicacions We denote by ex $(n; {C^3,C^4,…Cs})$ or fs(n) the maximum number of edges in a graph of order n and girth at least s+1. First we give a method to transform an n-vertex graph of girth g into a graph of girth at least g-1 on fewer vertices. For an infinite sequence of values of n and s∈{4, 6, 10} the obtained graphs are denser than the known constructions of graphs of the same girth s+1. We also give another different construction of dense graphs for an infinite sequence of values of n and s∈{7, 11}. These two methods improve the known lower bounds on fs(n) for s ∊ {4, 6, 7, 10, 11} which were obtained using different algorithms. Finally, to know how good are our results, we have proved that $\limsup_{n\longrightarrow{\infty}}\displaystyle\frac{\int_s (n)}{n^{1+\displaystyle\frac{2}{s-1}}}=2^{-1-\displaystyle\frac{2}{s-1}}$ for s ∊ 2 {5, 7, 11}, and $s^{-1-\displaystyle\frac{2}{s}}$ ≤ $\limsup_{n\longrightarrow{\infty}}\displaystyle\frac{\int_s (n)}{n^{1+\displaystyle\frac{2}{s}}}$ ≤ 0.5 for s ∊ {6, 10}. Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafsGraph theoryAlgorithmsGrafs, Teoria deAlgorismes Attribution-NonCommercial-NoDerivs 3.0 Spain http://creativecommons.org/licenses/by-nc-nd/3.0/es/ info:eu-repo/semantics/publishedVersionArtículo

## Otros documentos del mismo autor/a

Araujo Pardo, M. Gabriela; Balbuena Martínez, Maria Camino Teófila
Balbuena Martínez, Maria Camino Teófila; Márquez, Alberto; Portillo, Jose Ramón
Balbuena Martínez, Maria Camino Teófila; García-Vázquez, Pedro
Balbuena Martínez, Maria Camino Teófila; Guevara, Mucuy-kak
Balbuena Martínez, Maria Camino Teófila; García-Vázquez, Pedro

Coordinación

Patrocinio