z-logo
open-access-imgOpen Access
Hypergraph 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$.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom