An extension of A.R. Rao’s characterization of potentially Km+1Km+1-graphic sequences

Let An=(a1,a2,…,an)An=(a1,a2,…,an) and Bn=(b1,b2,…,bn)Bn=(b1,b2,…,bn) be two sequences of nonnegative integers with a1≥a2≥⋯≥ana1≥a2≥⋯≥an, ai≤biai≤bi for i=1,2,…,ni=1,2,…,n and ai+bi≥ai+1+bi+1ai+bi≥ai+1+bi+1 for i=1,2,…,n−1i=1,2,…,n−1. (An;Bn)(An;Bn) is said to be potentially  Km+1Km+1 (resp. Am+1Am+1)-graphic   if there exists a simple graph GG with vertices v1,v2,…,vnv1,v2,…,vn such that ai≤dG(vi)≤biai≤dG(vi)≤bi for i=1,2,…,ni=1,2,…,n and GG contains Km+1Km+1 as a subgraph (resp. the induced subgraph of {v1,v2,…,vm+1}{v1,v2,…,vm+1} in GG is Km+1Km+1), where Km+1Km+1 is the complete graph on m+1m+1 vertices. In this paper, we give a good characterization of (An;Bn)(An;Bn) that is potentially Am+1Am+1-graphic. As a corollary, we also obtain a good characterization of (An;Bn)(An;Bn) that is potentially Km+1Km+1-graphic if b1≥b2≥⋯≥bnb1≥b2≥⋯≥bn. This is an extension of A.R. Rao’s characterization of potentially Km+1Km+1-graphic sequences.