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$. There are a number of graphs on $k$ vertices and $j$ edges which contains a graph $Z_4$ but not contains a cycle on 4 vertices.

13 pages

References in corpus (1)

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