The smallest degree sum that yields potentially $K_{r+1}—Z$-graphical Sequences

Abstract

Let $K_m–H$ be the graph obtained from $K_m$ by removing the edges set $E(H)$ of the graph $H$ ($H$ is a subgraph of $K_m$). We use the symbol $Z_4$ to denote $K_4–P_2$. A sequence $S$ is potentially $K_m–H$-graphical if it has a realization containing a $K_m–H$ as a subgraph. Let $\sigma (K_m–H,n)$ denote the smallest degree sum such that every $n$-term graphical sequence $S$ with $\sigma (S)\ge \sigma (K_m–H,n)$ is potentially $K_m–H$-graphical. In this paper, we determine the values of $\sigma (K_{r+1}–Z,n)$ for $n\ge 5r+19,r+1\ge k\ge 5,j\ge 5$ where $Z$ is a graph on $k$ vertices and $j$ edges which contains a graph $Z_4$, but not contains a cycle on $4$ vertices. We also determine the values of $\sigma (K_{r+1}–Z_4,n)$, $\sigma (K_{r+1}–(K_4–e),n)$, $\sigma (K_{r+1}–K_4,n)$ for $n\ge 5r+16,r\ge 4$.