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: | 0 han comentado esto | 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: 54.198.142.121 (b988624a06)
Comentario
¿Cuánto es: diez mil + uno?

Busca en Cambalache


Blogalia


Se comenta en Cambalache

  • Nfer en Pobre buzón
  • Nfer en Pobre buzón
  • Anónima en Pobre buzón
  • Anónima en Pobre buzón
  • Anónima en Los numeros negativos y el deseo
  • Anónima en Tú es que nunca has tenido una ex
  • Zifra en Muerte en el olvido (Ángel González)
  • Mizar en La décima, la milonga y otros hermosos temas por Drexler.
  • Pedro en Mariposas Imposibles
  • Anónima en 10 de Marzo de 1991
  • Categorías:

    Archivos:

    <Septiembre 2018
    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