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

Subjects: Mathematics >> Discrete Mathematics and Combinatorics submitted time 2024-02-13

Chunhui LAI

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)\geq \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\geq 5r+19,  r+1 \geq k \geq 5,$  $j \geq 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\geq 5r+16, r\geq 4$.

YES

 Hits 1117  Downloads 244  Comment 0