Artículo
A sufficient degree condition for a graph to contain all trees of size k
Autor/es | Balbuena, Camino
Márquez Pérez, Alberto Portillo Fernández, José Ramón |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2011 |
Fecha de depósito | 2021-06-14 |
Publicado en |
|
Resumen | 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 ... 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 dG(x) + dG(y) ≥ 2k − 4 for all pairs x, y of nonadjacent neighbors of a vertex u of dG(u) ≥ k. |
Agencias financiadoras | Ministerio de Educación y Ciencia (MEC). España Generalitat de Catalunya Junta de Andalucía |
Identificador del proyecto | MTM2008-06620-C03-02
MTM2008-05866-C03-01 1298 SGR2009 P06-FQM-01649 |
Cita | Balbuena, C., Márquez Pérez, A. y Portillo Fernández, J.R. (2011). A sufficient degree condition for a graph to contain all trees of size k. Acta Mathematica Sinica, 27 (1), 135-140. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
A sufficient degree condition ... | 219.3Kb | [PDF] | Ver/ | |