Split hypergraphs

Details Split hypergraphs Split hypergraphs

2011-09-27

arxiv.org/abs/1109.6016v1

SIAM J. Discrete Math. (2008) 22, pp. 1155-1163

Mathematics

Combinatorics

13 pages

Scientific paper

Generalizing the notion of split graphs to uniform hypergraphs, we prove that the class of these hypergraphs can be characterized by a finite list of excluded induced subhypergraphs. We show that a characterization by generalized degree sequences is impossible, unlike in the well-known case of split graphs. We also give an algorithm to decide whether a given uniform hypergraph is a split hypergraph. If it is, the algorithm gives a splitting of it; the running time is $O(N\log N)$. These answer questions of Sloan, Gy. Tur\'an and Peled.

Affiliated with

Also associated with

No associations

Rating

Split hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Split hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Split hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-42100