Open AccessHypergraph domination and strong independence
Author(s) -
Bibin K. Jose,
Źsolt Tuza
Publication year - 2009
Publication title -
applicable analysis and discrete mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.69
H-Index - 26
eISSN - 2406-100X
pISSN - 1452-8630
DOI - 10.2298/aadm0902347j
Subject(s) - mathematics , hypergraph , combinatorics , independence number , disjoint sets , vertex (graph theory) , cardinality (data modeling) , order (exchange) , graph , domination analysis , upper and lower bounds , dominating set , simple (philosophy) , discrete mathematics , simple graph , mathematical analysis , finance , computer science , economics , data mining , philosophy , epistemology
We solve several conjectures and open problems from a recent paperby {sc Acharya} [{f 2}]. Some of our results are relatives ofthe Nordhaus--Gaddum theorem, concerning the sum of dominationparameters in hypergraphs and their complements. (A dominating setin $cH$ is a vertex set $Dssq X$ such that, for every vertex$xin Xsmin D$ there exists an edge $EincE$ with $xin E$ and$Ecap D ees$.) As an example, it is shown that the tight bound$gamma gamma (cH) + gamma gamma (overline{cH}) le n+2$holds in hypergraphs $cH=(X,cE)$ of order $nge 6$, where$overline{cH}$ is defined as $overline{cH} =(X,mathcal{overline{cE}}) $ with $mathcal{overline{E}} = { Xsmin E mid E in mathcal{E} }$, and $ggg$ is the minimumtotal cardinality of two disjoint dominating sets. We also presentsome simple constructions of balanced hypergraphs, disprovingconjectures of the aforementioned paper concerning stronglyindependent sets. (Hypergraph $cH$ is balanced if every odd cyclein $cH$ has an edge containing three vertices of the cycle; and aset $S subseteq X$ is strongly independent if $|Scap E|le 1$for all $EincE$.