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

Abstract

A keyring is a graph obtained from a cycle by appending $r\ge 0$ leaves to one of its vertices. Sidorenko proved an Erdős-Gallai-type theorem: Every graph of order $n$ and size more than $\frac{(k-1)n}{2}$ contains a keyring of size at least $k$ and with $r$ leaves for $r\le \frac{k-1}{2}$ (Theorem 1.4, An Erdős-Gallai-type theorem for keyrings, Graphs Combin., 2018). In this note, we show that Sidorenko's theorem holds for larger $r$ and so complete the Erdős-Gallai-type theorem for keyrings.

7