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) \geq 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, \quad \text{for } m \geq 3, n \geq 3m;\) \(\sigma(C_{2m+2}, n) = m(2n – m – 1) + 4, \quad \text{for } m \geq 3, n \geq 5m – 2. \)