Discrete Mathematics & Theoretical Computer Science, Vol 16, No 1 (2014)

Font Size:  Small  Medium  Large

A forcible version of Niessen's problem on degree sequences of graphs

Jiyun Guo, Jianhua Yin

Abstract


Let (a1,a2,…,an) and (b1,b2,…,bn) be two sequences of nonnegative integers satisfying the condition that b1≥b2≥⋯≥bn, ai≤ bi for i=1,2,…,n and ai+bi≥ai+1+bi+1 for i=1,2,…, n-1. In this paper, we give two different conditions, one of which is sufficient and the other one necessary, for the sequences (a1,a2,…,an) and (b1,b2,…,bn) such that for every (c1,c2,…,cn) with ai≤ci≤bi for i=1,2,…,n and ∑&limits;i=1n ci≡0 (mod 2), there exists a simple graph G with vertices v1,v2,…,vn such that dG(vi)=ci for i=1,2,…,n. This is a variant of Niessen's problem on degree sequences of graphs (Discrete Math., 191 (1998), 247 13;253).

Full Text: PDF PostScript