An extremal problem on the potentially \(P_k\)-graphic sequences (Q1971211)

A nonincreasing sequence \(\pi\) of \(n\) positive integers is potentially \(P_k\)-graphic if it is the degree sequence of some simple graph \(G\) of order \(n\) that contains a \(K_k\) as a subgraph. Denote \(\sigma(\pi)\) the sum of the terms of \(\pi\), and denote \(\sigma(k, n)\) the smallest \(\sigma(\pi)\) such that every \(\pi\) with \(\sigma(\pi) \geq \sigma(k,n)\) is potentially \(P_k\)-graphic. P. Erdős et al. (1991) conjectured that \(\sigma(k,n) = (k-1)(2n-k) + 2\). It is proved in this paper that (i) if \(k+1 \leq n \leq 2k\), then \(\sigma(k,n) = (k-1)(2n-k) + (n-k)(n-k-1) + 2\); and (ii) if \(n = 2k+1\), then \(\sigma(k,n) = (k-1)(2n-k) + k(k-1) + 2\). It is also proved that if \(n \geq 8\) then \(\sigma(3,n) = 4n-4\).