Embedding a forest in a graph

MaRDI QIDQ540102zbMATH OpenFDO

Authors Mark K. Goldberg, Malik Magdon-Ismail

Publication date 1 June 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.3882, https://eudml.org/doc/225937, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p99.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35)

Abstract: For math{pge 1}, we prove that every forest with math{p} trees whose sizes are $a_1,\mathrm{...},a_p$ can be embedded in any graph containing at least $su{m}_{i=1}^p(a_i+1)$ vertices and having a minimum degree at least $su{m}_{i=1}^p{a}_i$.

Recommendations

• Subtrees and subforests of graphs
• Maximum and minimum degree conditions for embedding trees
• Degree conditions for forests in graphs
• Degree conditions for embedding trees
• A note on uniquely embeddable forests

Cited in

(5)

• Forest-based networks
• Subtrees and subforests of graphs
• On the Turán number of forests
• scientific article; zbMATH DE number 7306903 (Why is no real title available?)
• A note on uniquely embeddable forests

This page was built for publication: Embedding a forest in a graph

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