SOME NP-COMPLETE PROBLEMS FOR HYPERGRAPH DEGREE SEQUENCES

A k-hypergraph G has vertex-set V(G) and edge-set E(G) consisting of k-subsets of V(G). If u epsilon V(G), then those edges of G containing u define a (k minus 1)-hypergraph G//u. We say G subsumes the (k minus 1)-hypergraphs left brace G//u vertical u epsilon V(G) right brace . Given n graphs (i. e. , 2-hypergraphs) g//1,g//2,. . . g//n, is there a 3-hypergraph G such that the subsumed graphs G//i congruent g//i, for i equals 1,2,. . . , n? Given only the degree sequences of n graphs g//1,g//2,. . . ,g//n, is there a 3-hypergraph G whose subsumed graphs G//1,G//2,. . . ,G//n have the same degree sequences? We consider 3-hypergraphs with and without repeated edges. We prove these problems NP-complete and indicate their relation to some well-known problems.