A sufficient degree condition for a graph to contain all trees of size k |
| |
Authors: | Camino Balbuena Alberto Márquez José Ramón Portillo |
| |
Affiliation: | 1.Departament de Matemàtica Aplicada III,Universitat Politècnica de Catalunya,Barcelona,Spain;2.Departamento de Matemática Aplicada I,Universidad de Sevilla,Sevilla,Spain |
| |
Abstract: | 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. |
| |
Keywords: | Erdos-Sos conjecture |
本文献已被 维普 SpringerLink 等数据库收录! |
|