A note on the characterization of potentially Kr+1- P k graphic sequences - Hu, Lili, (Utilitas Mathematica, 2014)
For given a graph H, a graphic sequence π = (d1, d 2, • • •, dn) is said to be potentially H-graphic if there exists a realization of π containing H as a subgraph. Let Pk, denote a path on k+1 vertices and Kr+1- P k(1 ≤ k ≤ r) be the graph obtained from Kr+1 by removing the k edges of Pk. If a graphic sequence πr = (d 1,d2, • • • ,dn) has a realization G with the vertex set V(G) = {v1,v2 ) • • •, un} such that dG(u i) = di for 1 ≤ i ≤ n and G[{u1,u 2, • • •,ur+1}] = Kr+1 Pfc(l < k ≤ r) such that dKr+1-pk(ui) = r for 1 ≤ i ≤ r- k, dkr+1-pk(ui) = r-1 for r- k + l<i<r k + 2 and dkr+1-pk (ui) = r- 2 for r-k+3 ≤ i ≤ r+1, then is said to be potentially Ar+1 -Pk-graphic. In this paper, we first characterize the potentially Ar+1 Pfc-graphic sequences which is analogous to Wang-Yin characterization [13] using a system of inequalities. Then we obtain a sufficient and necessary condition for a graphic sequence ir to have a realization containing Kr+1- Pk as an induced subgraph. Moreover, we characterize potentially Kr+1 P4-graphic sequences.