Rooted Spider Embeddings and the Erd\H os-Sós Conjecture

Abstract

Under a local density condition, we prove that every $k$-edge spider embeds at any prescribed center of degree at least $k$, unless all legs are even and the host graph has one of two specified structures. These structures contain complete bipartite subgraphs with prescribed neighborhoods. The proof uses path rerouting and three exchange lemmas that describe equality in neighborhood estimates. As a consequence, we recover the Erd\H os-Sós bound for all spiders.

arXiv comment24 pages, no figures. V3: Title revised to emphasize rooted embeddings. The main proof strategy is retained from V2. Arguments for previously omitted cases have been added, definitions clarified, and the exposition and references updated

Cited by in corpus (1)

• An Erdős-Gallai-type theorem for keyrings with larger number of leaves