

























A keyring is a graph obtained from a cycle by appending $r\ge0$ 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。