The representation of multi-hypergraphs by set intersections

• Autorzy: Stanisław Bylka , Jan Komar
• Języki publikacji: EN

Abstrakty

EN

This paper deals with weighted set systems (V,𝓔,q), where V is a set of indices, $𝓔 ⊂ 2^V$ and the weight q is a nonnegative integer function on 𝓔. 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,𝓔,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 each E ∈ 𝓔.
A necessary condition for the existence of such representation is the monotonicity of q on 𝓔 i.e., if F ⊂ 𝓔 then q(F) ≥ q(𝓔). 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.

Słowa kluczowe

EN

intersection graph; intersection hypergraph

Kategorie tematyczne

• 05C62: Graph representations (geometric and intersection representations, etc.) {For graph drawing, see also }
• 05C65: Hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2007
• Tom: 27
• Numer: 3
• Strony: 565-582

Daty

wydano

2007

otrzymano

2006-02-13

poprawiono

2007-10-24

zaakceptowano

2007-10-24

Twórcy

autor

Stanisław Bylka

• Institute of Computer Science, Polish Academy of Sciences, 21 Ordona street, 01-237 Warsaw, Poland

autor

Jan Komar

• Institute of Computer Science, Polish Academy of Sciences, 21 Ordona street, 01-237 Warsaw, Poland

Bibliografia

• [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.

Identyfikatory

DOI

10.7151/dmgt.1383