کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419353 | 683788 | 2014 | 9 صفحه PDF | دانلود رایگان |
The question of necessary and sufficient conditions for the existence of a simple hypergraph with a given degree sequence is a long-standing open problem. Let ψm(n)ψm(n) denote the set of all degree sequences of simple hypergraphs on vertex set [n]={1,2,⋯,n}[n]={1,2,⋯,n} that have mm edges. A simple characterisation of ψm(n)ψm(n) is defined in terms of its upper and/or lower elements (degree sequences). In the process of finding all upper degree sequences, a number of results have been achieved in this paper. Classes of upper degree sequences with lowest rank (sum of degrees) rminrmin and with highest rank rmaxrmax have been found; in the case of rminrmin, the unique class of isomorphic hypergraphs has been determined; the case of rmaxrmax leads to the simple uniform hypergraph degree sequence problem. A smaller generating set has been found for ψm(n)ψm(n). New classes of upper degree sequences have been generated from the known sequences in dimensions less than nn.
Journal: Discrete Applied Mathematics - Volume 163, Part 2, 30 January 2014, Pages 205–213