zbMATH — the first resource for mathematics

New results on degree sequences of uniform hypergraphs. (English) Zbl 1295.05081
Summary: A sequence of nonnegative integers is $$k$$-graphic if it is the degree sequence of a $$k$$-uniform hypergraph. The only known characterization of $$k$$-graphic sequences is due to A. K. Dewdney [Proc. Am. Math. Soc. 53, 535–540 (1975; Zbl 0323.05137)]. As this characterization does not yield an efficient algorithm, it is a fundamental open question to determine a more practical characterization. While several necessary conditions appear in the literature, there are few conditions that imply a sequence is $$k$$-graphic. In light of this, we present sharp sufficient conditions for $$k$$-graphicality based on a sequence’s length and degree sum. W. Kocay and P. C. Li [Ars Comb. 82, 145–157 (2007; Zbl 1174.05088)] gave a family of edge exchanges (an extension of 2-switches) that could be used to transform one realization of a 3-graphic sequence into any other realization. We extend their result to $$k$$-graphic sequences for all $$k \geq 3$$. Finally we give several applications of edge exchanges in hypergraphs, including generalizing a result of A. H. Busch et al. [J. Graph Theory 70, No. 1, 29–39 (2012; Zbl 1243.05191)] on packing graphic sequences.

MSC:
 05C07 Vertex degrees 05C65 Hypergraphs
Full Text: