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$.

5 pages

References in corpus (1)

• A note on potentially $K_4-e$ graphical sequences

Cited by in corpus (1)

• Exact solution to an extremal problem on graphic sequences with a realization containing every $2$-tree on $k$ vertices