Upper Bounds for the Domination Numbers of Graphs Using Turán's Theorem and Lovász Local Lemma.

Let G be a connected graph of order n with vertex set V(G). For positive integers a and b, a subset S ⊆ V (G) is an (a, b)-dominating set if every vertex v ∈ S is adjacent to at least a vertices inside S and every vertex v ∈ V \ S is adjacent to at least b vertices inside S. The minimum cardinality of an (a, b)-dominating set for G is called the (a, b)-domination number of G and is denoted by γ a , b (G) . There are various results on upper bounds for γ a , b (G) when G is a regular graph or a and b are small numbers. In the first part of this paper, for a given graph G with the minimum degree of at least max { a , b } , we define a new graph G ′ associated to G and show that the independence number of this graph is related to γ a , b (G) . In the next part, using Lovász local lemma, we give a randomized approach to improve previous results on the upper bounds for γ a , b (G) in some special cases. [ABSTRACT FROM AUTHOR]