Title:
On the Set of Simple Hypergraph Degree Sequences
Author:
Type:
Uncontrolled Keywords:
hypergraph ; degree sequence ; complement
Abstract:
For a given m, 0 < m ≤ 2 n, let Dm (n) denote the set of all hypergraphic sequences for hypergraphs with n vertices and m hyperedges. A hypergraphic sequence in Dm (n) is upper hypergraphic if all its components are at least m/2. Let ^Dm (n) denote the set of all upper hypergraphic sequences. A structural characterization of the lowest and highest rank maximal elements of ^Dm (n) was provided in an earlier study. In the current paper we present an analogous characterization for all upper non-hypergraphic sequences. This allows determining the thresholds r ̅ min and r�� such that all upper sequences of ranks lower than r ̅ min are hypergraphic and all sequences of ranks higher than r�� are non-hypergraphic.
Publisher:
Date submitted:
Date of publication:
DOI:
ISSN:
Other identifier:
Language:
Journal or Publication Title:
Volume:
Number:
URL:
Additional Information:
Affiliation:
Institute for Informatics and Automation Problems