Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

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

Abstract : 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 ∑&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–253).
Document type :
Journal articles
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download
Contributor : Hélène Lowinger Connect in order to contact the contributor
Submitted on : Wednesday, July 22, 2015 - 9:14:51 AM
Last modification on : Thursday, September 7, 2017 - 1:03:40 AM
Long-term archiving on: : Friday, October 23, 2015 - 10:23:50 AM


Publisher files allowed on an open archive




Jiyun Guo, Jianhua yin. A variant of Niessen’s problem on degree sequences of graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (1), pp.287--292. ⟨10.46298/dmtcs.1260⟩. ⟨hal-01179211⟩



Record views


Files downloads