članak: 1 od 1  
Applicable Analysis and Discrete Mathematics
2009, vol. 3, br. 2, str. 347-358
jezik rada: engleski
članak
doi:10.2298/AADM0902347J

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či

Balanced hypergraph; strongly independent set; inverse domination number; independent domination number; disjoint domination number

Reference

Acharya, B.D. (2007) Domination in hypergraphs. AKCE J. Combin, 4:2, 117-126
Acharya, B.D. (2008) Domination in hypergraphs II: New directions. u: Proc. Int. Conf. - ICDM Mysore, India, str. 1-16
Bacsó, G. (2009) Complete description of forbidden subgraphs in the structural domination problem. Discrete Mathematics, 309(8): 2466
Berge, C. (1989) Hypergraphs: Combinatorics of finite sets. Amsterdam
Bibin, J.K., Germina, K.A., Kumar, A. On some open problems of stable sets and domination in hypergraphs. AKCE J. Combin, Submitted
Haynes, T.W., Hedetniemi, S.T., Slater, P.J. (1998) Fundamentals of domination in graphs. New York: Marcel Dekker
Tuza, Z. (2008) Hereditary domination in graphs: characterization with forbidden induced subgraphs. SIAM Journal on Discrete Mathematics, 22(3): 849