A variant of Niessen's problem on degree sequences of graphs

作者：Guo, Ji-Yun; Yin, Jian-Hua^*

来源：Discrete Mathematics and Theoretical Computer Science, 2014, 16(1): 287-292.

• graph
• degree sequence
• Niessen's problem

Let (a(1), a(2), ... , a(n)) and (b(1), b(2), ... , b(n)) be two sequences of nonnegative integers satisfying the condition that b(1) >= b(2) >= ... >= b(n), a(i) <= b(i) for i = 1, 2, ... , n and a(i) + b(i) > a(i+1) + b(i+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 (a(1), a(2), ... , a(n)) and (b(1), b(2), ... , b(n)) such that for every (c(1), c(2), ... , c(n)) with a(i) <= c(i) <= b(i) for i = 1, 2, ... , n and Sigma(n)(i-1)c(i) equivalent to 0 (mod 2), there exists a simple graph G with vertices v(1), v(2), ... , v(n) such that d(G)(v(i)) = c(i); for i = 1, 2, ..., n. This is a variant of Niessen's problem on degree sequences of graphs (Discrete Math., 191 (1998), 247-253).

• 出版日期2014
• 单位海南大学