Applicable Analysis and Discrete Mathematics 2009, vol. 3, br. 2, str. 347-358
|
|
Hypergraph domination and strong independence
(naslov ne postoji na srpskom)
aPost Graduate Department of Mathematics, St. Dominic's College Kanjirappally, Kerala, India bComputer and Automation Institute, Hungarian Academy of Sciences, Budapest, Hungary + Department of Computer Science and Systems Technology, University of Pannonia, Veszprém, Hungary
e-adresa: bibinkjose2002@yahoo.com, tuza@sztaki.hu
Sažetak(ne postoji na srpskom) We solve several conjectures and open problems from a recent paper by Acharya [2]. Some of our results are relatives of the Nordhaus-Gaddum theorem, concerning the sum of domination parameters in hypergraphs and their complements. (A dominating set in H is a vertex set D X such that, for every vertex xЄ X\D there exists an edge E Є E with x Є E and E∩D ≠Ø.) As an example, it is shown that the tight bound γγ(H)+γγ(H) ≤ n+2 holds in hypergraphs H = (X, E) of order n ≥ 6, where H is defined as H = (X, E) with E = {X\E | E Є E}, and γγ is the minimum total cardinality of two disjoint dominating sets. We also present some simple constructions of balanced hypergraphs, disproving conjectures of the aforementioned paper concerning strongly independent sets. (Hypergraph H is balanced if every odd cycle in H has an edge containing three vertices of the cycle; and a set S X is strongly independent if |S∩E|≤ 1 for all E Є E.).
Ključne rečiBalanced hypergraph; strongly independent set; inverse domination number; independent domination number; disjoint domination number
|