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).
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 1 (in progress) (1), pp.287--292
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01179211
Contributeur : Hélène Lowinger <>
Soumis le : mercredi 22 juillet 2015 - 09:14:51
Dernière modification le : jeudi 7 septembre 2017 - 01:03:40
Document(s) archivé(s) le : vendredi 23 octobre 2015 - 10:23:50

Fichier

dmtcs-16-1-16.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

75

Téléchargements de fichiers

225