On a Characterization for a Graphic Sequence to be Potentially \(K_{r+1} – E(G)\)-graphic

Abstract

Let \(G\) be a subgraph of the complete graph \(K_{r+1}\) on \(r+1\) vertices, and let \(K_{r+1} – E(G)\) be the graph obtained from \(K_{r+1}\) by deleting all edges of \(G\). A non-increasing sequence \(\pi = (d_1, d_2, \ldots, d_n)\) of nonnegative integers is said to be potentially \(K_{r+1} – E(G)\)-graphic if it is realizable by a graph on \(n\) vertices containing \(K_{r+1} – E(G)\) as a subgraph. In this paper, we give characterizations for \(\pi = (d_1, d_2, \ldots, d_n)\) to be potentially \(K_{r+1} – E(G)\)-graphic for \(G = 3K_2, K_3, P_3, K_{1,3}\), and \(K_2 \cup P_2\), which are analogous to Erdős-Gallai’s characterization using a system of inequalities. These characterizations partially answer one problem due to Lai and Hu [10].