Cambalache 3,14 - La vidriera irrespetuosa


Que el mundo fue y será una porquería, ya lo sé.

A sufficient degree condition for a graph to contain all trees of size k

Acta Mathematica Sinica Volume 27, Number 1, 135-140, DOI: 10.1007/s10114-011-9617-6

A sufficient degree condition for a graph to contain all trees of size k

Camino Balbuena, Alberto Márquez and José Ramón Portillo

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: Erdős-Sós conjecture

MR(2000) Subject Classification 05C05 - 05C07 - 05C35

2010-12-23 14:38 | Categoría: | Enlace permanente | Etiquetas: | Y dicen por ahí

Referencias (TrackBacks)

URL de trackback de esta historia http://zifra.blogalia.com//trackbacks/68522

Comentarios

Nombre
Correo-e
URL
Dirección IP: 34.204.194.190 (a213c68988)
Comentario
¿Cuánto es: diez mil + uno?

Busca en Cambalache


Blogalia


Categorías:

Archivos:

<Septiembre 2019
Lu Ma Mi Ju Vi Sa Do
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30            

Lista de Enlaces

De interés

E-góticos

Mis otros

FotoFlickr


Blogalia



Versión para la columna lateral


zifra. Get yours at bighugelabs.com/flickr
2003-2006 Zifra Powered by Blogalia