Let @math be a connected graph of order @math with vertex set @math . A subset @math is an @math -dominating set if every vertex @math is adjacent to at least @math vertices in @math and every @math is adjacent to at least @math vertices in @math . The minimum cardinality of an @math -dominating set of @math is the @math -domination number of @math , denoted by @math . There are various results about upper bounds for @math when @math is regular or @math and @math are small numbers. In the first part of this paper, for a given graph @math with the minimum degree of @math , we define a new graph @math associated to @math and show that the independence number of this graph is related to @math . In the next part, using Lov 'asz local lemma, we give a randomized approach to improve previous results in some special cases.
Let @math be a 3-uniform hypergraph of order @math and size @math , and let @math be a subset of vertices of @math . The set @math is a strong transversal in @math if @math contains at least two vertices from every edge of @math . The strong transversal number @math of @math is the minimum size of a strong transversal in @math . We show that @math , and we characterize the hypergraphs that achieve equality in this bound. In particular, we show that the Fano plane is the only connected 3-uniform hypergraph @math of order @math and size @math that achieves equality in this bound. A set @math of vertices in a graph @math is a double total dominating set of @math if every vertex of @math is adjacent to at least two vertices in @math . The minimum cardinality of a double total dominating set of @math is the double total domination number @math of @math . Let @math be a connected graph of order @math with minimum degree at least three. As an application of our hypergraph results, we show that @math with equality if and only if @math is the Heawood graph (equivalently, the incidence bipartite graph of the Fano plane). Further if @math is not the Heawood graph, we show that @math , while if @math is a cubic graph different from the Heawood graph, we show that @math , and this bound is sharp.