The Smallest Degree Sum that Yields Potentially $C_k$-graphical Sequences

Abstract

In this paper we consider a variation of the classical Turán-type extremal problems. Let $S$ be an $n$-term graphical sequence, and $\sigma (S)$ be the sum of the terms in $S$. Let $H$ be a graph. The problem is to determine the smallest even $l$ such that any $n$-term graphical sequence $S$ having $\sigma (S)\ge l$ has a realization containing $H$ as a subgraph. Denote this value $l$ by $\sigma (H,n)$. We show $\sigma (C_{2m+1},n)=m(2n–m–1)+2,\text{for }m\ge 3,n\ge 3m;$ $\sigma (C_{2m+2},n)=m(2n–m–1)+4,\text{for }m\ge 3,n\ge 5m–2.$