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

https://hal.inria.fr/hal-01179211
Contributor : Hélène Lowinger <>
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

File

dmtcs-16-1-16.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01179211, version 1

Collections

Citation

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 (in progress) (1), pp.287--292. ⟨hal-01179211⟩

Share

Metrics

Record views

146

Files downloads

774