To access the full text documents, please follow this link:

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
Springer Verlag

Show full item record

Related documents

Other documents of the same author

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
Balbuena Martínez, Maria Camino Teófila; Montejano, Luis P.
Balbuena Martínez, Maria Camino Teófila; Marcote Ordax, Francisco Javier; González Moreno, Diego Antonio
Araujo Pardo, M. Gabriela; Balbuena Martínez, Maria Camino Teófila