On $\alpha$-Domination in Graphs

Abstract

Let $G=(V,E)$ be an isolate-free graph. For some $\alpha$ with $0<\alpha \le 1$, a subset S of V is said to be an $\alpha$ -dominating set if for all $v \in V {\setminus } S, |N(v)\cap S|\ge \alpha |N(v)|$. The size of a smallest such S is called the $\alpha$ -domination number and is denoted by $\gamma _{\alpha }(G)$. A set $S\subseteq V$ is said to be an $\alpha$ -rate dominating set of G if for any vertex $v \in V$, $|N[v] \cap X|\ge \alpha |N(v)|$. The minimum cardinality of an $\alpha$-rate dominating set of G is called the $\alpha$ -rate domination number $\gamma _{\times \alpha }(G)$. The set of distinct values of $\gamma _\alpha (G)$ as $\alpha$ runs over (0, 1] is called the $\alpha$-domination spectrum of a graph G, i.e., $\mathsf {Sp}_\alpha (G) = \{\gamma _\alpha (G): \alpha \in (0,1]\}$. In this paper, we study some properties of $\mathsf {Sp}_\alpha (G)$ and show that $\gamma _\alpha (G)$ changes its value only at rational points as $\alpha$ runs over (0, 1]. Using this result, we characterize some values of $\alpha$ such that $\gamma _\alpha (G) \le n\alpha$, where n is the number of vertices in G, holds. Finally, we present some improved probabilistic upper bounds of $\alpha$-domination number and $\alpha$-rate domination number of a graph G.

1 Introduction

The domination in graphs has been an active area of research from the time of its inception. Two domination books [8, 9] provide a comprehensive report of vastness of the area of the domination and its relation to other graph parameters. Many variations of the domination problem can be found in literature most of which are motivated by many real-life scenarios. One such variation is $\alpha$-domination in graphs, introduced by Dunbar et al. [6]. The concept of $\alpha$-domination also models some problems in the spread of diseases or influence in social or virtual networks (see [5, 10]). Subsequent works on $\alpha$-domination can be found in [3, 4, 7, 11,12,13]. In the current paper, we introduce the notion of $\alpha$-domination spectrum of a graph G and using it, we show that $\gamma _\alpha (G)$, the $\alpha$-domination number changes its value only at rational points as $\alpha$ runs over (0, 1] and demonstrate some extremal graphs with respect to critical values.

In [4], the authors proved that for all $\alpha \in (0,1)$ and for all $\epsilon >0$, $\gamma _\alpha (G)\le n\alpha +\epsilon$, where n is the number of vertices in G, holds for all graphs G with sufficiently large minimum degree. On the other hand, authors in [13] characterized the values of $\alpha$ for a particular class of graphs such that $\gamma _\alpha (G)\le n\alpha$ holds. We show that for certain values of $\alpha$, a tighter upper bound $\gamma _\alpha (G)\le n\alpha$ holds. It is to be noted here, in contrast with [13], that our results hold good for all graphs.

Finally, we present some improved probabilistic upper bounds of $\gamma _\alpha (G)$ and $\gamma _{\times \alpha }(G)$. Throughout the paper, we assume that G is an isolate-free graph. For standard graph-theoretic terminologies, please refer to [16], and for the probabilistic methods terminologies, please refer to [1].

1.1 Preliminaries

Let $G=(V,E)$ be an isolate-free simple undirected graph.¹ For any vertex $v \in V$, N(v) denotes the set of all vertices adjacent to v, $N[v]=N(v)\cup \{v\}$ and $\deg (v)=|N(v)|$. For some $\alpha$ with $0<\alpha \le 1$, a subset S of V is said to be an $\alpha$ -dominating set of G if for all $v \in V {\setminus } S, |N(v)\cap S|\ge \alpha |N(v)|$. The size of a smallest such set S is called the $\alpha$ -domination number and is denoted by $\gamma _{\alpha }(G)$. An $\alpha$-dominating set of size $\gamma _{\alpha }(G)$ is called a $\gamma _{\alpha }(G)$-set or $\gamma _{\alpha }$-set. A set $S\subseteq V$ is said to be an $\alpha$ -rate dominating set of G if for any vertex $v \in V$, $|N[v] \cap X|\ge \alpha |N(v)|$. The minimum cardinality of an $\alpha$-rate dominating set of G is called the $\alpha$ -rate domination number and is denoted by $\gamma _{\times \alpha }(G)$. Assume that $V=\{v_1,v_2,\ldots ,v_n\}$ and $d_i=\deg (v_i)$ for $i=1,2,\ldots ,n$. For $0 < \alpha \le 1$, the $\alpha$ -degree of a graph G is defined as follows:

$$\begin{aligned} \widehat{d}_{ \alpha }= \widehat{d}_{ \alpha }(G) = \frac{1}{n}\sum _{i=1}^n\biggl (\begin{array}{c} d_i \\ \lceil \alpha d_i\rceil -1 \end{array}\biggr ). \end{aligned}$$

The closed $\alpha$ -degree of a graph G is defined as follows:

$$\begin{aligned} \widetilde{d}_{ \alpha }= \widetilde{d}_{ \alpha }(G) = \frac{1}{n}\sum _{i=1}^n\biggl (\begin{array}{c} d_i+1 \\ \lceil \alpha d_i\rceil -1 \end{array}\biggr ). \end{aligned}$$

It is known that for any isolate-free graph G of order n, $\gamma (G)\le \gamma _\alpha (G)\le \beta (G)$, where $\beta (G)$ is the vertex covering number of G. Define $\alpha$-domination spectrum of a graph G, denoted by $\mathsf {Sp}_\alpha (G)$, to be the set of distinct values of $\gamma _\alpha (G)$ as $\alpha$ runs over (0, 1], i.e., $\mathsf {Sp}_\alpha (G) = \{\gamma _\alpha (G): \alpha \in (0,1]\}$. Now, two cases may arise: either $\mathsf {Sp}_\alpha (G)$ is singleton or not. It is known that if for a graph G, $\gamma (G) =\beta (G)$, then $\gamma (G)= \gamma _\alpha (G)= \beta (G)$, i.e., $|\mathsf {Sp}_\alpha (G)|=1$. Examples of graphs with singleton $\alpha$-domination spectrum are star graphs $K_{1,n-1}$.

On the other hand, if $\gamma (G) < \beta (G)$, then for $0<\alpha \le 1/\Delta , \gamma _\alpha (G)=\gamma (G)$ and for $1-1/\Delta <\alpha \le 1, \gamma _\alpha (G)=\beta (G)$. Thus for $\Delta \ge 2$, we have $\gamma (G),\beta (G) \in \mathsf {Sp}_\alpha (G)$, i.e., $|\mathsf {Sp}_\alpha (G)|\ge 2$. The complete graph $K_n$ has a $\alpha$-domination spectrum of size $n-1$, i.e., $\mathsf {Sp}_\alpha (K_n) \subseteq \{1,2,\ldots ,n-1\}$. Thus, the only case left is when $\Delta =1$. However, if G is an isolate-free graph and $\Delta =1$, then G is a disjoint union of a copies of $P_2$. Thus in this case we have $\gamma (G)=\beta (G)$. Thus for an isolate-free graph G, $|\mathsf {Sp}_\alpha (G)|>1$ implies $\gamma (G) \ne \beta (G)$ and $\Delta \ge 2$.

2 $\alpha$-Domination Spectrum of a Graph and its Consequences

In this section, we focus on the case when $\mathsf {Sp}_\alpha (G)$ is not singleton, i.e., $|\mathsf {Sp}_\alpha (G)|>1$. For the sake of clarity, we assume that the elements in $\mathsf {Sp}_\alpha (G)$ are arranged in ascending order. Now, we move towards proving our main result that the $\alpha$-domination number changes its value only at rational points as $\alpha$ runs over (0, 1]. However before doing that, we prove a lemma which we will use later.

Lemma 2.1

Let G be a graph such that $|\mathsf {Sp}_\alpha (G)|>1$. Let $q\in \mathsf {Sp}_\alpha (G)$ such that $q\ne \gamma (G)$. Let $A=\{\alpha \in (0,1]:\gamma _\alpha (G)<q\}$ and $B=\{\alpha \in (0,1]:\gamma _\alpha (G)\ge q\}$. Then there exists a rational number $\alpha ^*\in (0,1)$ such that $A=(0,\alpha ^*]$ and $B=(\alpha ^*,1]$.

Proof

Since $q \ne \gamma (G)$, q is not the least element of $\mathsf {Sp}_\alpha (G)$. Observe that both A and B are non-empty, because $(0,1/\Delta ]\subseteq A$ and $(1-1/\Delta ,1]\subseteq B$. In fact, both A and B are intervals. Because if $a,b \in A$ with $a<b$, then for any c with $a<c<b$, we have $c \in A$. It follows from the fact that $\alpha '<\alpha ''$ implies $\gamma _{\alpha '}(G)\le \gamma _{\alpha ''}(G)$. Moreover, from the definition, it follows that $A\cup B=(0,1]$ and $A\cap B=\emptyset$. Thus there exists $\alpha ^* \in (0,1]$ such that either $A=(0,\alpha ^*), B=[\alpha ^*,1]$ or $A=(0,\alpha ^*], B=(\alpha ^*,1]$.

Claim 1

Both A and B are left-open, right-closed intervals, i.e., $A=(0,\alpha ^*]$ and $B=(\alpha ^*,1]$.

Proof of Claim 1

If possible, let $A=(0,\alpha ^*)$ and $B=[\alpha ^*,1]$. Let $p\in \mathsf {Sp}_\alpha (G)$ be the largest element in $\mathsf {Sp}_\alpha (G)$ less than q. Thus there exists $\alpha ' \in A$ such that $\gamma _{\alpha '}(G)=p$. This imply that for all $\alpha \in [\alpha ',\alpha ^*), \gamma _\alpha (G)=p$. Let $(\alpha _n)$ be a strictly monotonically increasing sequence in $[\alpha ',\alpha ^*)$ such that $(\alpha _n)$ converges to $\alpha ^*$. Now as $\alpha _n \in [\alpha ',\alpha ^*)$, we have $\gamma _{\alpha _n}=p$, i.e., for each $\alpha _n$, there exists $S_n \subseteq V$ with $|S_n|=p$ such that

$$\begin{aligned} \dfrac{|N(v)\cap S_n|}{|N(v)|}\ge \alpha _n,\quad \forall v \in V{\setminus } S_n. \end{aligned}$$

Moreover as $|S_n|=p<q$, $S_n$ is not a $\gamma _{\alpha ^*}$-set, i.e., there exists at least one $v_n \in V{\setminus } S_n$ such that

$$\begin{aligned} \dfrac{|N(v_n)\cap S_n|}{|N(v_n)|}< \alpha ^*. \end{aligned}$$

Thus we get a sequence of $S_n$ of subsets of V and a sequence of vertices $v_n \in V {\setminus } S_n$ such that

$$\begin{aligned} \alpha _n \le \dfrac{|N(v_n)\cap S_n|}{|N(v_n)|}< \alpha ^*,\quad \forall n \in \mathbb {N} \end{aligned}$$

(1)

As G is a finite graph, the number of choices for subsets $S_n$ of size p and the number of choices for $v_n \in V {\setminus } S_n$ is finite. Thus, the sequence $\left( \frac{|N(v_n)\cap S_n|}{|N(v_n)|}\right)$ assumes finitely many values. Now, since $(\alpha _n)$ converges to $\alpha ^*$, by Sandwich Theorem, the sequence $\left( \frac{|N(v_n)\cap S_n|}{|N(v_n)|}\right)$ converges to $\alpha ^*$. As any convergent sequence taking finitely many values is eventually constant, we have $\left( \frac{|N(v_n)\cap S_n|}{|N(v_n)|}\right)$ to be eventually a constant sequence. Thus there exists $k \in \mathbb {N}$ such that $\frac{|N(v_n)\cap S_n|}{|N(v_n)|}=\alpha ^*$ for all $n \ge k$. This is a contradiction to Eq. (1). Thus our claim is justified and hence $A=(0,\alpha ^*]$ and $B=(\alpha ^*,1]$.

Claim 2

$\alpha ^* \in \mathbb {Q}$, where $\mathbb {Q}$ denote the set of all rationals.

Proof of Claim 2

If possible, let $\alpha ^* \in (0,1]{\setminus } \mathbb {Q}$. We observe that $\gamma _{\alpha ^*}(G)=p$, because if $\gamma _{\alpha ^*}(G)<p$, then for all $\alpha \in A$, $\gamma _\alpha (G)<p$ which contradicts the fact that $p\in \mathsf {Sp}_\alpha (G)$. Since, $\alpha ^*$ is an irrational number, $\alpha ^* |N(v)|$ is not an integer for all $v \in V$. Now as $(0,1]\cap (\mathbb {R}{\setminus } \mathbb {Q})$ is dense in (0, 1], there exists an irrational number $\overline{\alpha }\in (0,1]\cap (\mathbb {R}{\setminus } \mathbb {Q})$ with $\overline{\alpha }>\alpha ^*$ such that $\lceil \alpha ^* |N(v)|\rceil =\lceil \overline{\alpha } |N(v)|\rceil$ for all $v \in V$ (we omit the details of the proof).

Now let S be a $\gamma _{\overline{\alpha }}$-set of G. Then for all $v \in V{\setminus } S$, $|N(v)\cap S|\ge \overline{\alpha } |N(v)|$. As $\overline{\alpha }\in \mathbb {R}{\setminus } \mathbb {Q}$, we have $v \in V{\setminus } S$, $|N(v)\cap S|\ge \lceil \overline{\alpha } |N(v)|\rceil =\lceil \alpha ^* |N(v)|\rceil \ge \alpha ^* |N(v)|$. Thus S is a $\gamma _{\alpha ^*}$-set in G and hence $|S|=p$.

On the other hand, as $\overline{\alpha }>\alpha ^*,\overline{\alpha } \in B$. But S being a $\gamma _{\overline{\alpha }}(G)$-set of G, we get $|S|\ge q$ (by definition of B). This is a contradiction. Hence $\alpha ^* \in \mathbb {Q}$. $\square$

Now we are in a position to prove the following theorem.

Theorem 2.1

Let G be a graph such that $\mathsf {Sp}_\alpha (G)=\{a_1,a_2,\ldots ,a_t\}$ with $\gamma (G)=a_1<a_2< \cdots <a_t=\beta (G)$ and $t>1$. Then there exists $t-1$ rational numbers $\alpha _1< \alpha _2< \cdots <\alpha _{t-1}$ in $(0,1)\cap \mathbb {Q}$ such that

• 1. for all $\alpha \in (0,\alpha _1]$, $\gamma _\alpha (G)=a_1$.

• 2. for all $i \in \{1,2,\ldots ,t-2\}$, for all $\alpha \in (\alpha _i,\alpha _{i+1}]$, $\gamma _\alpha (G)=a_{i+1}$.

• 3. for all $\alpha \in (\alpha _{t-1},1]$, $\gamma _\alpha (G)=a_t$.

Proof

Substituting $q=a_t$ in Lemma 2.1, we get a rational number $\alpha _{t-1}$ such that $A_1=\{\alpha \in (0,1]:\gamma _\alpha (G)< a_t\}=(0,\alpha _{t-1}]$ and $B_1=\{\alpha \in (0,1]:\gamma _\alpha (G)\ge a_t\}=(\alpha _{t-1},1]$. However, as $a_t$ is the largest element in $\mathsf {Sp}_\alpha (G)$, we have $B_1=\{\alpha \in (0,1]:\gamma _\alpha (G)= a_t\}=(\alpha _{t-1},1]$.

Again, substituting $q=a_{t-1}$ in Lemma 2.1, we get a rational number $\alpha _{t-2}$ such that $A_2=\{\alpha \in (0,1]:\gamma _\alpha (G)< a_{t-1}\}=(0,\alpha _{t-2}]$ and $B_2=\{\alpha \in (0,1]:\gamma _\alpha (G)\ge a_{t-1}\}=(\alpha _{t-2},1]$. However, as $a_t$ and $a_{t-1}$ are the only two elements in $\mathsf {Sp}_\alpha (G)$ which are greater or equal to $a_{t-1}$ and $B_1=\{\alpha \in (0,1]:\gamma _\alpha (G)= a_t\}=(\alpha _{t-1},1]$, we have $\{\alpha \in (0,1]:\gamma _\alpha (G)= a_{t-1}\}=(\alpha _{t-2},\alpha _{t-1}]$.

Continuing in this way, at one stage we substitute $q=a_2$ in Lemma 2.1 to get a rational number $\alpha _1$ such that $A_{t-1}=\{\alpha \in (0,1]:\gamma _\alpha (G)< a_2\}=(0,\alpha _{1}]$ and $B_{t-1}=\{\alpha \in (0,1]:\gamma _\alpha (G)\ge a_{2}\}=(\alpha _1,1]$. By similar argument as that of above, we get $\{\alpha \in (0,1]:\gamma _\alpha (G)= a_{2}\}=(\alpha _{1},\alpha _{2}]$. Moreover, as $\gamma (G)=a_1$ is the only value in $\mathsf {Sp}_\alpha (G)$ which is less than $a_2$, we have $A_{t-1}=\{\alpha \in (0,1]:\gamma _\alpha (G)= a_1\}=(0,\alpha _{1}]$. Hence the theorem follows. $\square$

We call the $\alpha _i$’s obtained in Theorem 2.1 as critical values of $\alpha$. A typical $\alpha$ vs $\gamma _\alpha (G)$-plot, as demonstrated in Theorem 2.1, is shown in Fig. 1. It is shown in Theorem 2.4 that for any finite set of rational numbers in (0, 1), there exists a graph G which has that set as the set of its all critical values. Moreover, Theorem 2.1 has an immediate corollary.

Fig. 1

A typical $\alpha$-vs-$\gamma _\alpha$ plot

Corollary 2.2

Let G be a graph and $\overline{\alpha }$ be a irrational number in (0, 1). Then there exists $\epsilon >0$, such that for all $\alpha \in (\overline{\alpha }-\epsilon ,\overline{\alpha }+\epsilon )$, $\gamma _\alpha (G)$ is constant.

Proof

The corollary follows from Theorem 2.1 and denseness of rationals and irrationals in $\mathbb {R}$. $\square$

Our next goal is to find an upper bound on the size of the $\alpha$-domination spectrum of a graph. Before that we prove a lemma and recall the definition of totient summatory function $\Phi$.

Lemma 2.3

Let G be a graph such that $\mathsf {Sp}_\alpha (G)=\{a_1,a_2,\ldots ,a_t\}$ with $a_1<a_2< \ldots <a_t$ and let $\alpha _i$’s be as in Theorem 2.1. Then for each $\alpha _i$, there exists a $\gamma _{\alpha _i}(G)$-set $S_i \subseteq V$ and a vertex $v_i \in V {\setminus } S_i$ such that

$$\begin{aligned} \alpha _i=\frac{|N(v_i)\cap S_i|}{|N(v_i)|}. \end{aligned}$$

Proof

Since $S_i$ is a $\gamma _{\alpha _i}(G)$-set of G, we have $|S_i|=a_i$ and

$$\begin{aligned} \frac{|N(v)\cap S_i|}{|N(v)|}\ge \alpha _i, \quad \forall v \in V {\setminus } S_i. \end{aligned}$$

(2)

If possible, for all $v \in V {\setminus } S_i$, the inequality in Eq. (2) is strict. But in that case, by denseness of real numbers, we can find $\alpha '>\alpha _i$ such that $\frac{|N(v)\cap S_i|}{|N(v)|}\ge \alpha '> \alpha _i$, for all $v \in V {\setminus } S_i.$ Thus $S_i$ is a $\gamma _{\alpha '}(G)$-set of G and hence $\gamma _{\alpha '}(G)\le |S_i|=a_i<a_{i+1}$. However as $\alpha '> \alpha _i$, we have $\gamma _{\alpha '}(G)\ge a_{i+1}$. This is a contradiction. Thus, there exists at least one vertex $v_i \in V {\setminus } S_i$ such that Eq. (2) holds with equality. Hence the theorem follows. $\square$

Definition 2.1

The totient summatory function $\Phi$ is defined as

$$\begin{aligned} \Phi (n)=\sum _{k=1}^{n} \phi (k), \end{aligned}$$

where $\phi$ is the Euler’s totient function, i.e., $\phi (k)$ is the number of positive integers less than and relatively prime to k.

Theorem 2.2

For any isolate-free graph G, the critical values belong to the set $\{\frac{p}{q}:gcd(p,q)=1; 1 \le p < q \le \Delta \}$ and $|\mathsf {Sp}_\alpha (G)|\le \Phi (\Delta )$, where $\Phi$ is the totient summatory function.

Proof

By Lemma 2.3, for every critical value $\alpha _i$, there exists a $\gamma _{\alpha _i}(G)$-set $S_i \subseteq V$ and a vertex $v_i \in V {\setminus } S_i$ such that

$$\begin{aligned} \alpha _i=\frac{|N(v_i)\cap S_i|}{|N(v_i)|}. \end{aligned}$$

Thus the first part of the theorem follows from the observation that $|N(v_i)\cap S_i|<|N(v_i)| \le \Delta$.

For the second part, observe that $|\{\frac{p}{q}:gcd(p,q)=1; 1 \le p < q \le \Delta \}|=\phi (2)+\phi (3)+\cdots +\phi (\Delta )$. Also note that $|\mathsf {Sp}_\alpha (G)|$ is one more than the number of critical values. Thus, $|\mathsf {Sp}_\alpha (G)|\le 1+\phi (2)+\phi (3)+\cdots +\phi (\Delta )= \Phi (\Delta )$. $\square$

Corollary 2.4

For a k-regular graph, the critical values belong to the set $\{\frac{p}{k}:1 \le p < k\}$ and $|\mathsf {Sp}_\alpha (G)|\le k$. $\square$

Remark 2.1

As $\gamma (G)\le \gamma _\alpha (G) \le \beta (G)$, we also have $|\mathsf {Sp}_\alpha (G)|\le \beta (G) -\gamma (G)+1$. Theorem 2.3 shows that this bound is tight. Also this upper bound provides an idea if both $\beta (G)$ and $\gamma (G)$ are known. Moreover, comparing this upper bound with the upper bound given in Theorem 2.2, it is observed that this upper bound is tighter if the difference between $\beta (G)$ and $\gamma (G)$ is smaller than $\Phi (\Delta )$. However, if $\Delta$ is relatively small compared to the difference between $\beta (G)$ and $\gamma (G)$, then the upper bound in Theorem 2.2 is tighter.

Theorem 2.3

Given any two natural numbers $r<s$, there exists an isolate-free graph G with $\gamma (G)=r,\beta (G)=s$ and $|\mathsf {Sp}_\alpha (G)|= s -r+1$, i.e., all the integer values between r and s (including both) are the $\alpha$-domination number $\gamma _\alpha (G)$ of G for some $\alpha \in (0,1]$.

Proof

Let $p=s-r+2$ and G be the disjoint union of $r-1$ copies of $K_2$ and one copy of $K_p$. Then $\gamma (G)=r$ and $\beta (G)=(p-1)+(r-1)=(s-r+1)+(r-1)=s$. Now, the degree of all the vertices in $r-1$ copies of $K_2$ are 1 and the degree of all the vertices in $K_p$ are $p-1$. Thus for any integer between r and s, say k, consider the set $S_k$ consisting of one vertex from each $K_2$ and $k-r+1$ vertices from $K_p$. Then $|N(v)\cap S_k|=1$ or $k-r+1$ according as v is a vertex in $K_2$’s outside $S_k$ or $K_p$ outside $S_k$. Let $\alpha =\frac{k-r+1}{p-1}<1$. Then $|N(v)\cap S_k|\ge \alpha |N(v)|$ for all $v \in V{\setminus } S_k$. Thus $\gamma _\alpha (G) \le |S_k|=k$. If possible, let $\gamma _\alpha (G) <k$ and let S be a $\gamma _\alpha (G)$-set in G. Since $\gamma (G)\le \gamma _\alpha (G)$ and all minimum dominating sets of G must contain exactly one vertex from each copy of $K_2$, S contains less than $k-r+1$ vertices from $K_p$. Thus, for all vertices v in $K_p$ outside S, we have $\alpha |N(v)|=\frac{k-r+1}{p-1} (p-1)=k-r+1>|N(v)\cap S|$. Thus S is not a $\gamma _\alpha (G)$-set of G, a contradiction. Therefore $\gamma _\alpha (G) =k$ and hence the theorem follows. $\square$

Theorem 2.4

Given any finite set of rational numbers $\alpha _1< \alpha _2< \cdots < \alpha _{t-1}$ in (0, 1) and any positive integer r, there exists an isolate-free graph G such that $\gamma (G)=r$ and $\alpha _i$’s are critical values for G.

Proof

Without loss of generality, let the $\alpha _i$’s have a common denominator, i.e., let $\alpha _i=\frac{s_i}{q}$, where $s_1<s_2<\cdots <s_{t-1}$. Now in the construction of G in the proof of Theorem 2.3, set $r=r$ and $s=q+r-1$. Therefore $p=q+1$. Let $k_i=s_i+r-1$. Then as in Theorem 2.3, $S_{k_i}$ is a $\alpha _i$-dominating set, where $\alpha _i=\frac{k_i-r+1}{p-1}=\frac{s_i}{q}$. Moreover, each $\alpha _i$ is a critical value in the $\alpha$-domination spectrum of G and $\gamma (G)=r$. $\square$

Proposition 2.5

Let G be a connected regular graph. Then $|\mathsf {Sp}_\alpha (G)|\ge 2$ if and only if G is not isomorphic to $K_2$ or $C_4$.

Proof

The proposition follows from Theorem 2.5 in [14], which states that for a connected graph G, $\gamma (G)=\beta (G)$ if and only if G is isomorphic to $K_2$ or $C_4$. $\square$

Corollary 2.6

For a connected k-regular graph which is not isomorphic to $K_2$ or $C_4$, $2 \le |\mathsf {Sp}_\alpha (G)|\le k$.

Proof

The proof follows from Corollary 2.4 and Proposition 2.5. $\square$

2.1 A Tighter Upper Bound

In [4], the authors proved that if G is a graph of order n and $\alpha \in (0,1)$, then $\gamma _\alpha (G)\le \left( 1-\frac{1}{\lceil \frac{1}{1-\alpha } \rceil } \right) n$. They also proved (Theorem 2.6 in [4]) that for all $\alpha \in (0,1)$ and for all $\epsilon >0$, $\gamma _\alpha (G)\le n\alpha +\epsilon$ holds for all graphs G with sufficiently large minimum degree (depending upon $\alpha$ and $\epsilon$). On the other hand, the authors in [13] [see Concluding Remarks (1)] characterized the values of $\alpha$ for a particular class of graphs such that $\gamma _\alpha (G)\le n\alpha$ holds. In this section, using the idea of critical values, we show that for certain values of $\alpha$, a tighter upper bound $\gamma _\alpha (G)\le n\alpha$ holds. It is to be noted here, in contrast with [13], that our results hold good for all graphs. We start by observing that if $\alpha =\frac{k}{k+1}$ for some $k \in \mathbb {N}$, then the upper bound in [4] reduces to $\gamma _\alpha (G)\le n\alpha$.

Theorem 2.5

Let G be a graph of order n, $k\in \mathbb {N}$ and $\alpha _i$’s be the critical values of $\alpha$ as defined in Theorem 2.1. If $\frac{k}{k+1} \in (\alpha _i,\alpha _{i+1}]$, then either $\gamma _\alpha (G)\le n\alpha$, for all $\alpha \in (\alpha _i,\alpha _{i+1}]$ or

$$\begin{aligned} \gamma _\alpha (G)= & {} n\alpha \,\, \text{ for } \text{ some } \,\,\alpha \in \left( \alpha _i,\frac{k}{k+1}\right) \,\, \text{ and } \,\,\\&\gamma _\alpha (G)\le n\alpha , \quad \forall \alpha \in \left[ \frac{k}{k+1},\alpha _{i+1}\right] . \end{aligned}$$

Proof

Since $\alpha _i$’s are the critical values, $\gamma _\alpha (G)$ remains constant in the interval $(\alpha _i,\alpha _{i+1}]$. Also $\gamma _{k/(k+1)}(G)\le \frac{nk}{k+1}$. Let $\alpha \in \left( \frac{k}{k+1},\alpha _{i+1}\right]$. Then $\gamma _\alpha (G)=\gamma _{k/(k+1)}(G)\le \frac{nk}{k+1}\le n\alpha$. If $\gamma _\alpha (G)\le n\alpha$, for all $\alpha \in (\alpha _i,\alpha _{i+1}]$, then the theorem holds. If not, then there exists $\alpha '\in (\alpha _i,\frac{k}{k+1})$ such that $\gamma _{\alpha '}(G)>n\alpha '$. As $\gamma _\alpha (G)$ remains constant in the interval $(\alpha _i,\alpha _{i+1}]$ (i.e., $\gamma _{\alpha '}(G)=\gamma _{k/(k+1)}(G)$), $\gamma _{k/(k+1)}(G)\le \frac{nk}{k+1}$ and $\gamma _{\alpha '}(G)>n\alpha '$, there exists $\alpha \in \left( \alpha ',\frac{k}{k+1}\right)$ such that $\gamma _\alpha (G)=n\alpha$. Hence the theorem follows. $\square$

3 New Probabilistic Upper Bounds

In this section, we prove some improved probabilistic upper bounds of $\alpha$-domination number and $\alpha$-rate domination number of a graph G. Gagarin, Poghosyan and Zverovich obtained the following probabilistic upper bounds for the $\alpha$-domination number of a graph.

Theorem 3.1

(Gagarin, Poghosyan, Zverovich [7]) For any graph G,

$$\begin{aligned} \gamma _{\alpha }(G)\le \biggl (1-\frac{\widehat{\delta }}{(1+\widehat{\delta })^{1+1/{\widehat{\delta }}}\widehat{d}_{\alpha }^{1/{\widehat{\delta }}}}\biggr )n, \end{aligned}$$

where $\widehat{\delta }=\lfloor \delta (1-\alpha )\rfloor +1$.

Corollary 3.1

(Gagarin, Poghosyan, Zverovich [7]) For any graph G,

$$\begin{aligned} \gamma _{\alpha }(G)\le \biggl [\frac{\ln (\widehat{\delta }+1)+\ln (\widehat{d}_{\alpha })+1}{\widehat{\delta }+1}\biggr ]n, \end{aligned}$$

where $\widehat{\delta }=\lfloor \delta (1-\alpha )\rfloor +1$.

Gagarin, Poghosyan and Zverovich obtained the following probabilistic upper bounds for the $\alpha$-rate domination number of a graph.

Theorem 3.2

(Gagarin, Poghosyan, Zverovich [7]) For any graph G,

$$\begin{aligned} \gamma _{\times \alpha }(G)\le \biggl (1-\frac{\widehat{\delta }}{(1+\widehat{\delta })^{1+1/{\widehat{\delta }}} \widetilde{d}_{\alpha }^{1/{\widehat{\delta }}}}\biggr )n, \end{aligned}$$

where $\widehat{\delta }=\lfloor \delta (1-\alpha )\rfloor +1$.

Corollary 3.2

(Gagarin, Poghosyan, Zverovich [7]) For any graph G,

$$\begin{aligned} \gamma _{\times \alpha }(G)\le \biggl (\frac{\ln (\widehat{\delta }+1)+\ln \widetilde{d}_{\alpha }+1}{\widehat{\delta }+1}\biggr )n, \end{aligned}$$

where $\widehat{\delta }=\lfloor \delta (1-\alpha )\rfloor +1$.

We obtain new probabilistic upper bounds for the $\alpha$-domination number of a graph, and improve Theorem 3.1 and Corollary 3.1. We also obtain new probabilistic upper bounds for the $\alpha$-rate domination number of a claw-free graph, and improve Theorem 3.2 and Corollary 3.2 for claw-free graphs. The following is useful.

Theorem 3.3

(Caro [2] and Wei [15]) For any graph G, $\alpha (G)\ge \sum _{v\in V(G)}\frac{1}{1+\deg (v)}$.

Theorem 3.4

For any graph G,

$$\begin{aligned} \gamma _{\alpha }(G)\le \biggl [1-\frac{\widehat{\delta }}{(1+\widehat{\delta })^{1+1/{\widehat{\delta }}} \widehat{d}_{\alpha }^{1/{\widehat{\delta }}}}\biggr ]n -\frac{n}{1+\Delta }\biggl [1-\biggl (\frac{1}{(1+\widehat{\delta }) \widehat{d}_{\alpha }} \biggr )^{\frac{1}{\widehat{\delta }}}\biggr ]^{1+\Delta }, \end{aligned}$$

where $\widehat{\delta }=\lfloor \delta (1-\alpha )\rfloor +1$.

Proof

We follow the proof of Theorem 3.1 given in [7]. Let A be a set formed by an independent choice of vertices of G, where each vertex is selected with probability

$$\begin{aligned} p=1-\biggl (\frac{1}{(1+\widehat{\delta }) \widehat{d}_{\alpha }} \biggr )^{\frac{1}{\widehat{\delta }}}. \end{aligned}$$

Let

$$\begin{aligned} B=\{v\in V(G)-A: |N(v_i)\cap A|\le \lceil \alpha d_i\rceil -1\}. \end{aligned}$$

Let $A'=\{v\in V(G):N[v]\subseteq A\}$, and I be a maximum independent set in $G[A']$. Clearly $(A-I)\cup B$ is an $\alpha$-dominating set for G. Thus $\gamma _{\alpha }(G) \le E(|(A-I)\cup B|)\le E(|A|)+E(|B|)-E(|I|)$. As it was shown in [7] (in the proof of Theorem 3.1),

$$\begin{aligned} E(|A|)+E(|B|)\le \biggl (1-\frac{\widehat{\delta }}{(1+\widehat{\delta })^{1+1/{\widehat{\delta }}} \widehat{d}_{\alpha }^{1/{\widehat{\delta }}}}\biggr )n. \end{aligned}$$

We compute the expectation of |I|. By Theorem 3.3,

$$\begin{aligned} E(|I|)\ge & {} E \biggl (\sum _{v\in A'}\frac{1}{1+\deg _{G[A']}(v)}\biggr )\\\ge & {} \sum _{v\in V}\frac{1}{1+\deg _{G}(v)}Pr(v\in A')\\= & {} \sum _{v\in V}\frac{1}{1+\deg _{G}(v)}p^{1+\deg _G(v)}\\\ge & {} \sum _{v\in V}\frac{1}{1+\deg _{G}(v)}p^{1+\Delta }\\\ge & {} \frac{n}{1+\Delta }p^{1+\Delta } = \frac{n}{1+\Delta } \biggl [1-\biggl (\frac{1}{(1+\widehat{\delta }) \widehat{d}_{\alpha }} \biggr )^{\frac{1}{\widehat{\delta }}}\biggr ]^{1+\Delta }. \end{aligned}$$

Thus the result follows immediately. $\square$

Following the proofs of Theorem 3.4 and Corollary 3.1 with $p=\frac{\ln (\widehat{\delta }+1)+\ln \widehat{d}_{\alpha }}{\widehat{\delta }+1}$, we obtain the following.

Corollary 3.3

For any graph G,

$$\begin{aligned} \gamma _{\alpha }(G)\le \biggl [\frac{\ln (\widehat{\delta }+1)+\ln \widehat{d}_{\alpha }+1}{\widehat{\delta }+1}\biggr ]n-\frac{n}{1+\Delta } \biggl (\frac{\ln (\widehat{\delta }+1)+\ln \widehat{d}_{\alpha }}{\widehat{\delta }+1}\biggr )^{1+\Delta }, \end{aligned}$$

where $\widehat{\delta }=\lfloor \delta (1-\alpha )\rfloor +1$.

We next present new probabilistic upper bounds for the $\alpha$-rate domination number in claw-free graphs.

Theorem 3.5

For any claw-free graph G,

$$\begin{aligned} \gamma _{\times \alpha }(G)\le \biggl [1-\frac{\widehat{\delta }}{(1+\widehat{\delta })^{1+1/{\widehat{\delta }}} \widetilde{d}_{\alpha }^{1/{\widehat{\delta }}}} \biggr ]n-\frac{n}{1+\Delta }\biggl [1-\biggl (\frac{1}{(1+\widehat{\delta }) \widetilde{d}_{\alpha }} \biggr )^{\frac{1}{\widehat{\delta }}}\biggr ]^{1+\Delta ^2}, \end{aligned}$$

where $\widehat{\delta }=\lfloor \delta (1-\alpha )\rfloor +1$.

Proof

We follow the proof of Theorem 3.2. Let A be a set formed by an independent choice of vertices of G, where each vertex is selected with probability

$$\begin{aligned} p=1-\biggl (\frac{1}{(1+\widehat{\delta })\widetilde{d}_{\alpha }} \biggr )^{\frac{1}{\widehat{\delta }}}. \end{aligned}$$

Let

$$\begin{aligned} B=\{v\in V(G): |N(v_i)\cap A|\le \lceil \alpha d_i\rceil -1\}. \end{aligned}$$

Let $A'=\{v\in V(G):N[v]\subseteq A\}$, $A''=\{v:N[v]\subseteq A'\}$, and let I be a maximum independent set in $G[A'']$. Clearly, $\deg _{G[A']}(v)=\deg (v)$ for every vertex $v\in A''$. Since G is claw-free, any vertex of $A'-A''$ is adjacent to at most one vertex of I. Then $(A-I)\cup B$ is an $\alpha$-rate dominating set for G. Thus $\gamma _{\times \alpha }(G) \le E(|(A-I)\cup B'|)=E(|A|+|B'|-|I|)= E(|A|)+E(|B'|)-E(|I|)$. As it was shown in [7] (in the proof of Theorem 3.2),

$$\begin{aligned} E(|A|)+E(|B|)\le \biggl (1-\frac{\widehat{\delta }}{(1+\widehat{\delta })^{1+1/{\widehat{\delta }}} \widetilde{d}_{\alpha }^{1/{\widehat{\delta }}}}\biggr )n. \end{aligned}$$

For a vertex v, if $N(v)=\{v_1,\ldots ,v_d\}$, then

$$\begin{aligned} Pr(v\in A'')=pp^{\deg (v_1)} \ldots p^{\deg (v_d)}\ge p^{1+d\Delta }\ge p^{1+\Delta ^2}. \end{aligned}$$

Thus,

$$\begin{aligned} E(|I|)\ge & {} E\biggl (\sum _{v\in A''}\frac{1}{1+\deg _{G[A'']}(v)}\biggr )\\\ge & {} \sum _{v\in V}\frac{1}{1+\deg _{G[A']}(v)}Pr(v\in A'')\\\ge & {} \sum _{v\in V}\frac{1}{1+\deg _{G}(v)}Pr(v\in A'')\\= & {} \sum _{v\in V}\frac{1}{1+\deg _{G}(v)}p^{1+\Delta ^2}\\\ge & {} \sum _{v\in V}\frac{1}{1+\deg _{G}(v)}p^{1+\Delta ^2}\\\ge & {} \frac{n}{1+\Delta }\biggl [1-\biggl (\frac{1}{(1+\widehat{\delta })\widetilde{d}_{\alpha }} \biggr )^{\frac{1}{\widehat{\delta }}}\biggr ]^{1+\Delta ^2}. \end{aligned}$$

$\square$

Following the proofs of Theorem 3.5 and Corollary 3.2 with $p=\frac{\ln (\widehat{\delta }+1)+ \ln \widetilde{d}_{\alpha }}{\widehat{\delta }+1}$, we obtain the following.

Corollary 3.4

For any claw-free graph G,

$$\begin{aligned} \gamma _{\times \alpha }(G)\le \biggl (\frac{\ln (\widehat{\delta }+1)+\ln (\widetilde{d}_{\alpha })+1}{\widehat{\delta }+1}\biggr )n-\frac{n}{1+\Delta } \biggl (\frac{\ln (\widehat{\delta }+1)+\ln \widetilde{d}_{\alpha }}{\widehat{\delta }+1}\biggr )^{1+\Delta ^2}, \end{aligned}$$

where $\widehat{\delta }=\lfloor \delta (1-\alpha )\rfloor +1$.

4 Conclusion and Open Problems

In this paper, we introduced the notion of $\alpha$-domination spectrum and critical values of $\alpha$ to prove a few bounds about $\gamma _\alpha (G)$ and the $\gamma _\alpha (G)$-spectrum of a graph G. Finally, we prove some improved probabilistic upper bounds of $\alpha$-domination number and $\alpha$-rate domination number of a graph G. We close with the following open problems.

• It was shown in [6], that $\alpha$-domination spectrum of cycles and paths have exactly two values, namely the domination number and vertex cover number of the respective graphs. It can be an interesting problem to characterize graphs with exactly two values in its $\alpha$-domination spectrum.

• In Theorem 2.5, certain values of $\alpha$’s were characterized for which $\gamma _\alpha (G)\le n\alpha$ holds. To characterize graphs G on n vertices for which $\gamma _\alpha (G)\le n\alpha$ holds for all $\alpha \in [1/n, 1]$ can be another interesting problem.