A characterization for a sequence to be potentially {Kr+1 - E(P2), K-2r+1}-graphic

Abstract

Let n ≥ r, πr = (d₁, d₂... ,d_n) be a non-increasing sequence of nonnegative integers and K_r+1 -E(P ₂) (resp. K^-2_r+1) be the graph obtained from K_r+1 by deleting two edges which are adjacent (resp. which are not adjacent). If π has a realization G containing K_r+1-E(P ₂) (resp. K^-2_r+1) as a subgraph, then π is said to be potentially K_r+1-E(P₂) (resp. K ^-2_r+1)-graphic. In this paper, we give a characterization for a sequence π to be potentially K_r+1 - E(P₂)-graphic and a characterization for a sequence π to be potentially K ^-2_r+1-graphic.