Embedding trees into graphs of large girth

DOI10.1016/S0012-365X(99)00354-4MaRDI QIDQ1567289zbMATH OpenOpenAlexWikidataFDO

Authors Penny Haxell, Tomasz Łuczak

Publication date 30 March 2001

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(99)00354-4

zbMATH Keywords

graph girthtree embeddings

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Review text

It is shown that for all except a finite number of pairs \((t,k)\) the following conjecture of Dobson holds: A tree \(T\) with \(k\) vertices can always be embedded into a graph of minimum degree \(\max\{\Delta(T), \lceil (k-1)/t \rceil \}\) and girth at least \(2t+1.\)

Recommendations

• On a conjecture about trees in graphs with large girth
• On graphs which contain each tree of given size
• Degree conditions for embedding trees
• Maximum and minimum degree conditions for embedding trees

Cited in

(12)

• Embedding meshes of trees into deBruijn graphs
• Subtrees and subforests of graphs
• On graphs which contain each tree of given size
• On a conjecture about trees in graphs with large girth
• Embedding trees in recursive circulants
• Tight bounds for embedding bounded degree trees
• A note on the Size-Ramsey number of long subdivisions of graphs
• Maximum and minimum degree conditions for embedding trees
• A randomized embedding algorithm for trees
• Tree embeddings and tree‐star Ramsey numbers
• Embedding trees with maximum and minimum degree conditions
• Oriented trees in digraphs without oriented 4-cycles

This page was built for publication: Embedding trees into graphs of large girth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1567289)