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

A sufficient degree condition for a graph to contain all trees of size k
Balbuena Martínez, Maria Camino Teófila; Márquez, Alberto; Portillo, Jose Ramón
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada III; Universitat Politècnica de Catalunya. COMBGRAF - Combinatòria, Teoria de Grafs i Aplicacions
The Erdős-Sós conjecture says that a graph G on n vertices and number of edges e(G) > n(k− 1)/2 contains all trees of size k. In this paper we prove a sufficient condition for a graph to contain every tree of size k formulated in terms of the minimum edge degree ζ(G) of a graph G defined as ζ(G) = min{d(u) + d(v) − 2: uv ∈ E(G)}. More precisely, we show that a connected graph G with maximum degree Δ(G) ≥ k and minimum edge degree ζ(G) ≥ 2k − 4 contains every tree of k edges if d G (x) + d G (y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of d G (u) ≥ k.
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria
Extremal problems (Mathematics)
Graph theory
Combinatorial analysis
Problemes extrems (Matemàtica)
Grafs, Teoria de
Anàlisi combinatòria
info:eu-repo/semantics/publishedVersion
Artículo
Springer Verlag
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Claverol Aguas, Mercè; Garijo, Delia; Grima, Clara; Márquez, Alberto; Seara Ojea, Carlos
Cortés, Carmen; Hurtado Díaz, Fernando Alfredo; Márquez, Alberto; Valenzuela, Jesús
Araujo Pardo, M. Gabriela; Balbuena Martínez, Maria Camino Teófila
Balbuena Martínez, Maria Camino Teófila; García-Vázquez, Pedro
Balbuena Martínez, Maria Camino Teófila; Cera, M; Diánez, A; García-Vázquez, P; Marcote Ordax, Francisco Javier