An Erdős-Gallai-type theorem for keyrings

DOI10.1007/S00373-018-1901-0zbMATH Open1395.05087arXiv1705.10254OpenAlexW3098414541MaRDI QIDQ2413630FDOQ2413630

Alexander Sidorenko

Publication date: 14 September 2018

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

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.

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

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\)

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• 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
• Asymptotic solution for a new class of forbidden r-graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

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)