An Extremal Problem On Potentially $K_{r+1}-H$-graphic Sequences

Abstract

Let $K_k$, $C_k$, $T_k$, and $P_k$ denote a complete graph on $k$ vertices, a cycle on $k$ vertices, a tree on $k+1$ vertices, and a path on $k+1$ vertices, respectively. 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$). 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}-H,n)$ for $n\ge 4r+10,r\ge 3,r+1\ge k\ge 4$ where $H$ is a graph on $k$ vertices which contains a tree on 4 vertices but not contains a cycle on 3 vertices. We also determine the values of $\sigma (K_{r+1}-P_2,n)$ for $n\ge 4r+8,r\ge 3$. There are a number of graphs on $k$ vertices which containing a tree on 4 vertices but not containing a cycle on 3 vertices (for example, the cycle on $k$ vertices, the tree on $k$ vertices, and the complete 2-partite graph on $k$ vertices, etc).

10 pages