Upper bounds for domination numbers of graphs using Turán's Theorem and Lovász local lemma

Abstract

Let $G$ be a connected graph of order $n$ with vertex set $V(G)$. A subset $S\subseteq V(G)$ is an $(a,b)$-dominating set if every vertex $v\in S$ is adjacent to at least $a$ vertices in $S$ and every $v\in V\setminus S$ is adjacent to at least $b$ vertices in $S$. The minimum cardinality of an $(a,b)$-dominating set of $G$ is the $(a,b)$-domination number of $G$, denoted by ${\gamma }_{a,b}(G)$. There are various results about upper bounds for ${\gamma }_{a,b}(G)$ when $G$ is regular or $a$ and $b$ are small numbers. In the first part of this paper, for a given graph $G$ with the minimum degree of $\max \{a,b\}$, we define a new graph $G^{\prime }$ associated to $G$ and show that the independence number of this graph is related to ${\gamma }_{a,b}(G)$. In the next part, using Lovász local lemma, we give a randomized approach to improve previous results in some special cases.