Embedding a Forest in a Graph

2010/11/17 by Mark Goldberg, Goldberg, Mark, Malik Magdon-Ismail +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1011.3882

Working paper, submitted

arxiv created 2010/11/17 · arxiv updated 2010/11/18

Abstract

For \mathp≥ 1, we prove that every forest with \mathp trees whose sizes are a₁,..., a_p can be embedded in any graph containing at least ∑_i=1^p (a_i + 1) vertices and having a minimum degree at least ∑_i=1^p a_i.

Related

• Maximum and minimum degree conditions for embedding trees
• A Caro-Wei bound for induced linear forests in graphs
• Degree conditions for embedding trees
• Linear arboricity of graphs with large minimum degree
• Degree powers in graphs with a forbidden forest