An Extremal Problem on Potentially $K_m-C_4$-Graphic Sequences

Abstract

A sequence $S$ is potentially $K_m-C_4$-graphical if it has a realization containing a $K_m-C_4$ as a subgraph. Let $\sigma (K_m-C_4,n)$ denote the smallest degree sum such that every $n$-term graphical sequence $S$ with $\sigma (S)\ge \sigma (K_m-C_4,n)$ is potentially $K_m-C_4$-graphical. In this paper, we prove that $\sigma (K_m-C_4,n)\ge (2m-6)n-(m-3)(m-2)+2$, for $n\ge m\ge 4$. We conjecture that equality holds for $n\ge m\ge 4$. We prove that this conjecture is true for $m=5$.