Characterizing \(K_{ r+1} – C_k\)-graphic Sequences

Abstract

For a given graph \(H\), a graphic sequence \(\pi = (d_1, d_2, \ldots, d_n)\) is said to be potentially \(H\)-graphic if there exists a realization of \(\pi\) containing \(H\) as a subgraph. Let \(K_{ r+1} – C_k\) be the graph obtained from \(K_{ r+1}\) by removing the \(k\) edges of a \(k\)-cycle. In this paper, we first characterize potentially \(A_{ r+1} – C_k\)-graphic sequences (\(3 \leq k \leq r+1\)), analogous to Yin et al.’s characterization [19], using a system of inequalities. Then, we obtain a sufficient and necessary condition for a graphic sequence \(\pi\) to have a realization containing \(K_{r+1} – C_k\) as an induced subgraph.