A note on the characterization of potentially Kr+1- P k graphic sequences

Abstract

For given a graph H, a graphic sequence π = (d₁, d ₂, • • •, d_n) is said to be potentially H-graphic if there exists a realization of π containing H as a subgraph. Let P_k, denote a path on k+1 vertices and K_r+1- P _k(1 ≤ k ≤ r) be the graph obtained from K_r+1 by removing the k edges of P_k. If a graphic sequence πr = (d ₁,d₂, • • • ,d_n) has a realization G with the vertex set V(G) = {v₁,v_2 ) • • •, u_n} such that d_G(u _i) = d_i for 1 ≤ i ≤ n and G[{u₁,u ₂, • • •,u_r+1}] = K_r+1 Pfc(l < k ≤ r) such that dK_r+1-p_k(ui) = r for 1 ≤ i ≤ r- k, dk_r+1-p_k(ui) = r-1 for r- k + l<i<r k + 2 and dk_r+1-p_k (u_i) = r- 2 for r-k+3 ≤ i ≤ r+1, then is said to be potentially A_r+1 -Pk-graphic. In this paper, we first characterize the potentially A_r+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 K_r+1- P_k as an induced subgraph. Moreover, we characterize potentially K_r+1 P₄-graphic sequences.