Characterizing Kr+1 - Ck-graphic Sequences

摘要

For given a graph H, a graphic sequence pi = (d(1), d(2), ... , d(n)) is said to be potentially H-graphic if there exists a realization of pi containing H as a subgraph. Let Kr+1 - C-k be the graph obtained from Kr+1 by removing the k edges of a k-cycle. In this paper, we first characterize potentially A(r+1)-C-k (3 <= k <= r+1) - graphic sequences which is analogous to Yin et.al 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 Kr+1 - C-k as an induced subgraph.