A Characterization on Potentially \(K_6 – C_4\)-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_m – H\) be the graph obtained from \(K_m\) by removing the edge set \(E(H)\), where \(H\) is a subgraph of \(K_m\). In this paper, we characterize the potentially \(K_6 – C_4\)-graphic sequences. This characterization implies a theorem due to Hu and Lai \([7]\).