Decompositions of hypergraphs into hyperstars

✍ Scribed by Zbigniew Lonc

• Publisher: Elsevier Science
• Year: 1987
• Tongue: English
• Weight: 630 KB
• Volume: 66
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(87)90128-2

✦ Synopsis

In the paper we investigate decompositions of hypergraphs into hyperstars. A hyperstar with center F and size c is every hypergraph (X, ~) such that F c_ n ~ and I~1 = c. A decomposition of a hypergraph (X, ~) into hypergraphs from a certain class YC is a family of hypergraphs {Hi = (X, ~i): i • I} such that {~i: i • I} is a partition of ~ and each Hi is isomorphic to a hypergraph in X.

In the paper we find necessary and sutiieient conditions for existence of a decomposition of a hypergraph into hyperstars with given centers and sizes. This result is then applied to obtain suttieient conditions for existence of a hyperstar decomposition of the hypergraphs Pm= (X, ~(X){~}) and K~,=(X, ~n(X)), IXl=m. As a corollary, these results give a partial solution of a problem of Yamamoto and Tazawa [7] related to hyperstar decompositions of K~,.