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) \geq \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 \geq 4r+10, r \geq 3, r+1 \geq k \geq 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 \geq 4r+8, r \geq 3\).