DMGT

Discussiones Mathematicae Graph Theory 27(3) (2007) 565-582
DOI: https://doi.org/10.7151/dmgt.1383

THE REPRESENTATION OF MULTI-HYPERGRAPHS BY SET INTERSECTIONS

Stanisław Bylka and Jan Komar

Institute of Computer Science
Polish Academy of Sciences
21 Ordona street, 01-237 Warsaw, Poland
e-mail: bylka@ipipan.waw.pl
e-mail: komjan@operamail.com

Abstract

This paper deals with weighted set systems (V,E,q), where V is a set of indices, E ⊂ 2^V and the weight q is a nonnegative integer function on E. The basic idea of the paper is to apply weighted set systems to formulate restrictions on intersections. It is of interest to know whether a weighted set system can be represented by set intersections. An intersection representation of (V,E,q) is defined to be an indexed family R = (R_v)_{v ∈ V} of subsets of a set S such that

⎢
⎢

∩
v ∈ E

R_v

⎢
⎢

= q(E) for eachE ∈ E.

A necessary condition for the existence of such representation is the monotonicity of q on E i.e., if F ⊂ E then q(F) ≥ q(E). Some sufficient conditions for weighted set systems representable by set intersections are given. Appropriate existence theorems are proved by construction of the solutions.

The notion of intersection multigraphs to intersection multi- hypergraphs - hypergraphs with multiple edges, is generalized. Some conditions for intersection multi-hypergraphs are formulated.

Keywords: intersection graph, intersection hypergraph.

2000 Mathematics Subject Classification: 05C62, 05C65.

References

[1]	C. Berge, Graphs and Hypergraphs (Amsterdam, 1973).
[2]	J.C. Bermond and J.C. Meyer, Graphe représentatif des aretes d'un multigraphe, J. Math. Pures Appl. 52 (1973) 229-308.
[3]	S. Bylka and J. Komar, Intersection properties of line graphs, Discrete Math. 164 (1997) 33-45, doi: 10.1016/S0012-365X(96)00041-6.
[4]	P. Erdös, A. Goodman and L. Posa, The representation of graphs by set intersections, Canadian J. Math. 18 (1966) 106-112, doi: 10.4153/CJM-1966-014-3.
[5]	F. Harary, Graph Theory (Addison-Wesley, 1969) 265-277.
[6]	V. Grolmusz, Constructing set systems with prescribed intersection size, Journal of Algorithms 44 (2002) 321-337, doi: 10.1016/S0196-6774(02)00204-3.
[7]	E.S. Marczewski, Sur deux properties des classes d'ensembles, Fund. Math. 33 (1945) 303-307.
[8]	A. Marczyk, Properties of line multigraphs of hypergraphs, Ars Combinatoria 32 (1991) 269-278. Colloquia Mathematica Societatis Janos Bolyai, 18. Combinatorics, Keszthely (Hungary, 1976) 1185-1189.
[9]	T.A. McKee and F.R. McMorris, Topics in Intersection Graph Theory, SIAM Monographs on Discrete Math. and Appl., 2 (SIAM Philadelphia, 1999).
[10]	E. Prisner, Intersection multigraphs of uniform hypergraphs, Graphs and Combinatorics 14 (1998) 363-375.

Received 13 February 2006
Revised 24 October 2007
Accepted 24 October 2007