The problem of efficiently characterizing degree sequences of simple hypergraphs (without repeated hyper-edges) is a fundamental long-standing open problem in Graph Theory. Several results are known for restricted versions of this problem. This paper adds to the list of sufficient conditions for a degree sequence to be hypergraphic and proposes a polynomial time algorithm which correctly identifies at least 2~((n-1)(n-2)/2) hypergraphic sequences. For comparison, the number of hypergraphic sequences on n vertices is at most 2~(n•(n-1).
展开▼
