PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2007 | 27 | 3 | 565-582
Tytuł artykułu

The representation of multi-hypergraphs by set intersections

Treść / Zawartość
Warianty tytułu
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
Wydawca
Rocznik
Tom
27
Numer
3
Strony
565-582
Opis fizyczny
Daty
wydano
2007
otrzymano
2006-02-13
poprawiono
2007-10-24
zaakceptowano
2007-10-24
Twórcy
  • Institute of Computer Science, Polish Academy of Sciences, 21 Ordona street, 01-237 Warsaw, Poland
autor
  • 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1383
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.