New results on degree sequences of uniform hypergraphs. (English) Zbl 1295.05081

Behrens, Sarah; Erbes, Catherine; Ferrara, Michael; Hartke, Stephen G.; Reiniger, Benjamin; Spinoza, Hannah; Tomlinson, Charles

Electron. J. Comb. 20, No. 4, Research Paper P14, 18 p. (2013).

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

Keywords:

degree sequence; hypergraph; edge exchange; packing