An Erdős-Gallai-type theorem for keyrings

DOI10.1007/S00373-018-1901-0MaRDI QIDQ2413630zbMATH OpenOpenAlexFDO

Authors Alexander Sidorenko

Publication date 14 September 2018

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.10254

zbMATH Keywords

Erdős-Sós conjectureErdős-Gallai theorem

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Abstract: A keyring is a graph obtained by appending $rgeq1$ leaves to one of the vertices of a cycle. We prove that for every $rleq(k-1)/2$, any graph with average degree more than $k-1$ contains a keyring with $r$ leaves and at least $k$ edges.

Recommendations

• Extremal graphs for blow-ups of keyrings
• Revisit of Erdős-Gallai's theorem on the circumference of a graph
• Stability in the Erdős-Gallai theorems on cycles and paths
• Cycles of Given Size in a Dense Graph
• The Erdős-Gallai theorem modulo \(k\)

Cites work

• scientific article; zbMATH DE number 431994 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• Asymptotic solution for a new class of forbidden r-graphs
• On maximal paths and circuits of graphs
• On the Erd�s-S�s conjecture
• Path Ramsey numbers in multicolorings
• The Erdős-Sós conjecture for spiders
• The Erdős‐Sós Conjecture for trees of diameter four

Cited in

(1)

• Embedding Graphs into Larger Graphs: Results, Methods, and Problems

This page was built for publication: An Erdős-Gallai-type theorem for keyrings

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