



















A non-increasing sequence $π=(d_1,\ldots,d_n)$ of nonnegative integers is said to be graphic if it is realizable by a simple graph $G$ on $n$ vertices. A graphic sequence $π=(d_1,\ldots,d_n)$ is said to be potentially $_3C_\ell$-graphic if there is a realization of $π$ containing cycles of every length $r$, $3\le r\le \ell$. It is well-known that if the non-increasing degree sequence $(d_1,\ldots,d_\ell)$ of a graph $G$ on $\ell$ vertices satisfies the Pósa condition that $d_{\ell+1-i}\ge i+1$ for every $i$ with $1\le i<\frac{\ell}{2}$, then $G$ is either pancyclic or bipartite. In this paper, we obtain a Pósa-type condition of potentially $_3C_\ell$-graphic sequences, that is, we prove that if $\ell\ge 5$ is an integer, $n\ge \ell$ and $π=(d_1,\ldots,d_n)$ is a graphic sequence with $d_{\ell+1-i}\ge i+1$ for every $i$ with $1\le i<\frac{\ell}{2}$, then $π$ is potentially $_3C_\ell$-graphic. This result improves a Dirac-type condition of potentially $_3C_\ell$-graphic sequences due to Yin et al. [Appl. Math. Comput., 353 (2019) 88--94], and asymptotically answers a problem due to Li et al. [Adv. Math., 33 (2004) 273--283]. As an application, this result also completely implies the value $σ(C_\ell,n)$ for $\ell\ge 5$ and $n\ge \ell$, improving the result of Lai [J. Combin. Math. Combin. Comput., 49 (2004) 57--64].
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。