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