New results on degree sequences of uniform hypergraphs (Q396927)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New results on degree sequences of uniform hypergraphs |
scientific article |
Statements
New results on degree sequences of uniform hypergraphs (English)
0 references
14 August 2014
0 references
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 \textit{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. \textit{W. Kocay} and \textit{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 \textit{A. H. Busch} et al. [J. Graph Theory 70, No. 1, 29--39 (2012; Zbl 1243.05191)] on packing graphic sequences.
0 references
degree sequence
0 references
hypergraph
0 references
edge exchange
0 references
packing
0 references
0 references
0 references