Geodesic
New results on degree sequences of uniform hypergraphs
Sarah Behrens1 ; Catherine Erbes2 ; Michael Ferrara2 ; Stephen G. Hartke1 ; Benjamin Reiniger3 ; Hannah Spinoza3 ; Charles Tomlinson1
1University of Nebraska-Lincoln
2University of Colorado Denver
3University of Illinois at Urbana-Champaign
The electronic journal of combinatorics, Tome 20 (2013) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 Dewdney in 1975. 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.Kocay and Li 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 Busch et al. on packing graphic sequences.
DOI : 10.37236/3414
Classification : 05C07, 05C65
Mots-clés : degree sequence, hypergraph, edge exchange, packing

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

1 University of Nebraska-Lincoln
2 University of Colorado Denver
3 University of Illinois at Urbana-Champaign 
@article{10_37236_3414,
     author = {Sarah Behrens and Catherine Erbes and Michael Ferrara and Stephen G. Hartke and Benjamin Reiniger and Hannah Spinoza and Charles Tomlinson},
     title = {New results on degree sequences of uniform hypergraphs},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {4},
     doi = {10.37236/3414},
     zbl = {1295.05081},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3414/}
}
TY  - JOUR
AU  - Sarah Behrens
AU  - Catherine Erbes
AU  - Michael Ferrara
AU  - Stephen G. Hartke
AU  - Benjamin Reiniger
AU  - Hannah Spinoza
AU  - Charles Tomlinson
TI  - New results on degree sequences of uniform hypergraphs
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3414/
DO  - 10.37236/3414
ID  - 10_37236_3414
ER  - 
%0 Journal Article
%A Sarah Behrens
%A Catherine Erbes
%A Michael Ferrara
%A Stephen G. Hartke
%A Benjamin Reiniger
%A Hannah Spinoza
%A Charles Tomlinson
%T New results on degree sequences of uniform hypergraphs
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/3414/
%R 10.37236/3414
%F 10_37236_3414
Sarah Behrens; Catherine Erbes; Michael Ferrara; Stephen G. Hartke; Benjamin Reiniger; Hannah Spinoza; Charles Tomlinson. New results on degree sequences of uniform hypergraphs. The electronic journal of combinatorics, Tome 20 (2013) no. 4. doi: 10.37236/3414

Cité par Sources :