On potentially $K_{r+1}-U$-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}-U,n)$ for $n\ge 5r+18,r+1\ge k\ge 7,$ $j\ge 6$ where $U$ is a graph on $k$ vertices and $j$ edges which contains a graph $K_3\bigcup P_3$ but not contains a cycle on 4 vertices and not contains $Z_4$. There are a number of graphs on $k$ vertices and $j$ edges which contains a graph $(K_3\bigcup P_3)$ but not contains a cycle on 4 vertices and not contains $Z_4$. (for example, $C_3\bigcup C_{i_1}\bigcup C_{i_2}\bigcup >...\bigcup C_{i_p}$ $(i_j\ne 4,j=2,3,...,p,i_1\ge 5)$, $C_3\bigcup P_{i_1}\bigcup P_{i_2}\bigcup ...\bigcup P_{i_p}$ $(i_1\ge 3)$, $C_3\bigcup P_{i_1}\bigcup C_{i_2}\bigcup >...\bigcup C_{i_p}$ $(i_j\ne 4,j=2,3,...,p,i_1\ge 3)$, etc)

10 pages

References in corpus (1)

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