An extremal problem on potentially $K_m-P_k$-graphic sequences

Abstract

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

5 pages