An Extremal Problem on the Potentially \(K_{r+1} – e\) Graphic Sequences

Abstract

Gould et al. (Combinatorics, Graph Theory and Algorithms, Vol. 1 (1999), 387-400) considered a variation of the classical Turén-type extremal problems as follows: for a given graph \(H\), determine the smallest even integer \(\sigma (H,n)\) such that every \(n\)-term positive graphic sequence \(\pi = (d_1, d_2, \ldots, d_n)\) with term sum \(\sigma(\pi) = d_1 + d_2 + \cdots + d_n \geq \sigma(H,n)\) has a realization \(G\) containing \(H\) as a subgraph. In particular, they pointed out that \(3n – 2 \leq \sigma(K_{4} – e, n) \leq 4n – 4\), where \(K_{r+1} – e\) denotes the graph obtained by removing one edge from the complete graph \(K_{r+1}\) on \(r+1\) vertices. Recently, Lai determined the values of \(\sigma(K_4 – e, n)\) for \(n \geq 4\). In this paper, we determine the values of \(\sigma(K_{r+1} – e, n)\) for \(r \geq 3\) and \(r+1 \leq n \leq 2r\), and give a lower bound of \(\sigma(K_{r+1} – e, n)\). In addition, we prove that \(\sigma(K_5 – e, n) = 5n – 6\) for even \(n\) and \(n \geq 10\) and \(\sigma(K_5 – e, n) = 5n – 7\) for odd \(n\) and \(n \geq 9\).