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
Autor/a:	Abajo, E.; Balbuena Martínez, Maria Camino Teófila; Diánez, A.
Otros autores:	Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada III; Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
Abstract:	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}.
Materia(s):	-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs -Graph theory -Algorithms -Grafs, Teoria de -Algorismes
Derechos:	Attribution-NonCommercial-NoDerivs 3.0 Spain http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Tipo de documento:	Artículo - Versión publicada Artículo
Compartir:

Mostrar el registro completo del ítem