Jiyun Guo ; Jianhua Yin - A variant of Niessen’s problem on degreesequences of graphs

dmtcs:1260 - Discrete Mathematics & Theoretical Computer Science, May 6, 2014, Vol. 16 no. 1 - https://doi.org/10.46298/dmtcs.1260
A variant of Niessen’s problem on degreesequences of graphsArticle

Authors: Jiyun Guo 1; Jianhua Yin 1

  • 1 Department of Mathematics, College of Information Science and Technology [Haikou]

Let (a1,a2,\textellipsis,an) and (b1,b2,\textellipsis,bn) be two sequences of nonnegative integers satisfying the condition that b1>=b2>=...>=bn, ai<= bi for i=1,2,\textellipsis,n and ai+bi>=ai+1+bi+1 for i=1,2,\textellipsis, 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,\textellipsis,an) and (b1,b2,\textellipsis,bn) such that for every (c1,c2,\textellipsis,cn) with ai<=ci<=bi for i=1,2,\textellipsis,n and &#x2211;&limits;i=1n ci=0 (mod 2), there exists a simple graph G with vertices v1,v2,\textellipsis,vn such that dG(vi)=ci for i=1,2,\textellipsis,n. This is a variant of Niessen\textquoterights problem on degree sequences of graphs (Discrete Math., 191 (1998), 247&#x2013;253).

Volume: Vol. 16 no. 1
Section: Graph Theory
Published on: May 6, 2014
Accepted on: July 23, 2015
Submitted on: July 21, 2013
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 796 times.
This article's PDF has been downloaded 432 times.