On graphs which contain each tree of given size

DOI10.1016/S0012-365X(97)84218-5MaRDI QIDQ1356784zbMATH OpenOpenAlexWikidataFDO

Authors Jean-François Saclé, Mariusz Woźniak

Publication date 25 November 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(97)84218-5

zbMATH Keywords

girthtree

Mathematics Subject Classification ID

Trees (05C05)

Review text

There is a conjecture by Dobson that a graph of sufficiently large girth and minimum degree contains each tree of a given size. In this sense, the paper proves that for a graph \(G\) with girth at least 7 and a tree \(T\) of size \(k\) the following holds: If the minimum degree of \(G\) is at least \(k/3\) and also at least the maximum degree of \(T\) then \(G\) contains \(T\).

Recommendations

• On a conjecture about trees in graphs with large girth
• Embedding trees into graphs of large girth
• A sufficient degree condition for a graph to contain all trees of size k
• On the Erdős-Sós conjecture and graphs with large minimum degree.
• A note on graphs containing all trees of a given size.

Cites work

• On the Erd�s-S�s conjecture
• Packing constants in graphs and connectivity
• The Erdös-Sós conjecture for graphs of girth 5

Cited in

(7)

• Expanding graphs contain all small trees
• Embedding trees into graphs of large girth
• On a conjecture about trees in graphs with large girth
• A note on graphs containing all trees of a given size.
• scientific article; zbMATH DE number 165095 (Why is no real title available?)
• A sufficient degree condition for a graph to contain all trees of size k
• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)

This page was built for publication: On graphs which contain each tree of given size

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