An extremal problem on potentially $K_{p_1,p_2,...,p_t}$-graphic sequences

Abstract

A sequence $S$ is potentially $K_{p_1,p_2,...,p_t}$ graphical if it has a realization containing a $K_{p_1,p_2,...,p_t}$ as a subgraph, where $K_{p_1,p_2,...,p_t}$ is a complete t-partite graph with partition sizes $p_1,p_2,...,p_t(p_1\ge p_2\ge ...\ge p_t\ge 1)$. Let $\sigma (K_{p_1,p_2,...,p_t},n)$ denote the smallest degree sum such that every $n$-term graphical sequence $S$ with $\sigma (S)\ge \sigma (K_{p_1,p_2,...,p_t},n)$ is potentially $K_{p_1,p_2,...,p_t}$ graphical. In this paper, we prove that $\sigma (K_{p_1,p_2,...,p_t},n)\ge 2[((2p_1+2p_2+...+2p_t-p_1-p_2-...-p_i-2)n-(p_1+p_2+...+p_t-p_i)(p_i+p_{i+1}+...+p_t-1)+2)/2]$ for $n\ge p_1+p_2+...+p_t,i=2,3,...,t.$

4 pages