Potentially \(K_{r+1}^{-p}\)-Graphic Sequences

Abstract

Let \(0 \leq p \leq [\frac{r+1}{2}]\) and \(\sigma(K_{r+1}^{-p},n)\) be the smallest even integer such that each \(n\)-term graphic sequence with term sum at least \(\sigma(K_{r+1}^{-p},n)\) has a realization containing \(K_{r+1}^{-p}\) as a subgraph, where \(K_{r+1}^{-p}\) is a graph obtained from a complete graph \(K_{r+1}\) on \(r+1\) vertices by deleting \(p\) edges which form a matching. In this paper, we determine \(\sigma(K_{r+1}^{-p},n)\) for \(r \geq 2, 1 \leq p \leq [\frac{r+1}{2}]\) and \(n \geq 3r + 3\). As a corollary, we also determine \(\sigma(K_{1^*,2^t}n)\) for \(t \geq 1\) and \(n \geq 3s + 6t\), where \(K_{1^*,2^t}\) is an \(r_1\times r_2\times \ldots \times r_{s+t}\) complete \((s + t)\)-partite graph with \(r_1 = r_2 = \ldots = r_s = 1\) and \(r_{s+1} = r_{s+2} = \ldots = r_{s+t} = 2\) and \(\sigma(K_{1^*,2^t},n)\) is the smallest even integer such that each \(n\)-term graphic sequence with term sum at least \(\sigma(K_{1^*,2^t},n)\) has a realization containing \(K_{1^*,2^t}\) as a subgraph.