(1, 2)-Domination in Graphs

Abstract

A (1, 2)-dominating set in a graph $G = (V, E)$ is a set having the property that for every vertex $v \in V-S$, there is at least one vertex in S at a distance 1 from v and a second vertex in S at a distance at most 2 from v. The $(1, 2)-$domination number of G, denoted by $\gamma _{1,2} (G)$, is the minimum cardinality of a $(1, 2)-$dominating set of G. In this paper, we have derived bounds of $\gamma _{1, 2}$ in terms of the order and the maximum degree. For trees, we get the bounds in terms of the number of pendant vertices. We have also characterized the graphs G of order n, for which $\gamma _{1, 2}(G) = n, n-1, n-2$.

1 Introduction

Hedetniemi et al. [3] introduced the concept of (1, k)-domination in graphs. Let k be a positive integer. A subset S of vertices is called a (1, k)-dominating set in G if for every vertex $v\in V-S$,  there are two distinct vertices $u, w \in S$ such that u is adjacent to v, and w is within distance k of v $(i.e.~ d_{G}(v, w) \le k)$. Hedetniemi et al. [4, 5] examined (1, k)-domination along with the internal distances in (1, k)-dominating sets. Factor and Langley [1, 2] studied (1, 2)-domination of digraphs.

In this paper, we study (1, 2)-domination in graphs. All our graphs are finite and simple.

2 Bounds of $\gamma _{1, 2}$ in terms of $\varDelta$

We start with the following observations.

Observation 1

For any two graphs G and H, $\gamma _{1,2}(G\cup H)=\gamma _{1,2}(G)+\gamma _{1,2}(H)$.

Observation 2

If H is a spanning supergraph of G, then $\gamma _{1, 2}(H)\le \gamma _{1, 2}(G)$.

Theorem 1

If G is a graph of order $n\ge 4$ with $\Delta (G) \ge n-2$, then

$$\begin{aligned} \gamma _{1, 2}(G) = \left\{ \begin{array}{ll} 2 &{}\quad \text{ if } G \text{ is } \text{ connected }\\ 3 &{}\quad \text{ if } G \text{ is } \text{ disconnected. } \end{array} \right. \end{aligned}$$

Proof

When $\Delta (G) = n-1$, let u be a full-degree vertex; and v be any other vertex in G. Then $\{ u, v\}$ is a (1, 2)-dominating set and so $\gamma _{1,2}$(G) =2.

When $\Delta (G) = n-2$, let u be a vertex of degree $n-2$; and v be the vertex which is not adjacent to u.

Case 1. G is connected.

Let w be a neighbour of v. Then $\{u, w \}$ is a (1, 2)-dominating set and so $\gamma _{1, 2}(G) =~2$.

Case 2. G is disconnected.

Then v is an isolated vertex. Let S be any (1, 2)-dominating set of G. Since every isolated vertex must lie in S, $\gamma _{1, 2}(G) \ge 3$. Clearly $\{u, v, x \}$ is a (1, 2)-dominating set for every $x\in N(u)$ and $\gamma _{1, 2}(G) = 3$.

Corollary 1

$\gamma _{1, 2}(G) = 2$ for the graphs $G = K_{n}, K_{1, n}, W_{n}, F_{n}$ and $H+K_{1}$ where H is any graph.

Theorem 2

Let G be a connected graph of order $n \ge 5$ with $2 \le \Delta (G) \le n-3$. Then $\gamma _{1, 2}(G) \le n- \Delta (G)$.

Proof

Let G be a connected graph with the given hypothesis. Let $\Delta (G) = n - 1 - k$. Then $2\le k \le n-3$ and $n-\Delta (G) = k +1$. Let $V(G) = \{u, v_{i}|1\le i\le n-1\}$, where u is a vertex of degree $\Delta (G)$, and $N(u) = \{v_{k+1}, v_{k+2},..., v_{n-1}\}$. Then $V(G) = N[u]\cup V_{1}$, where $V_{1} = \{v_{1}, v_{2},..., v_{k}\}$. Since G is connected, at least one vertex in $V_{1}$ has a neighbour in N(u).

Case 1. Every vertex in $V_{1}$ has some neighbour in N(u).

Without loss of generality, assume that $v_{i}$ is adjacent to $v_{j_{i}}$ in N(u), for $1\le i \le k$. The vertices $v_{j_{1}}, v_{j_{2}},..., v_{j_{k}}$ need not be distinct. Let $V_{2} =\{v_{j_{i}}|1 \le i \le k\}\subseteq N(u)$. Let $S = \{u, v_{j_{1}}, v_{j_{2}},..., v_{j_{k}}\} ( = V_{2} \cup \{u \})$.

Every vertex $v_{i} \in N(u)-S$ is adjacent to u and at a distance at most 2 from $v_{j_{1}}$. Every $v_{i} \in V_{1}$ is adjacent to $v_{j_{i}}$ and at a distance 2 from u. Hence S is a (1, 2)-dominating set and so $\gamma _{1, 2}(G) \le k+1$.

Case 2. Some vertex in $V_{1}$ has no neighbour in N(u).

Without loss of generality, let $V_{1}^{'} = \{v_{1}, v_{2},..., v_{r}\} \subseteq V_{1}$ be the set of vertices that have no neighbours in N(u). Let $V_{1}^{''} = V_{1} - V_{1}^{'} = \{ v_{r+1}, v_{r+2},..., v_{k}\}$. Then $V(G) = N[u]\cup V_{1}^{'}\cup V_{1}^{''}$. Since G is connected, at least one vertex in $V_{1}^{'}$ is adjacent to some vertex in $V_{1}^{''}$. Without loss of generality, let $v_{1}$ be adjacent to $v_{r+1}$. Without loss of generality, assume that $v_{i}$ is adjacent to $v_{j_{i}}$ in N(u), for $r+1\le i \le k$. The vertices $v_{j_{r+1}}, v_{j_{r+2}},..., v_{j_{k}}$ need not be distinct. Let $V_{2} =\{v_{j_{i}}|r + 1 \le i \le k\}\subseteq N(u)$.

Let $S = \{u, v_{j_{r+1}}, v_{j_{r+2}},..., v_{j_{k}}, v_{1}, v_{2},..., v_{r}\} (= V_{2} \cup V_{1}^{'} \cup \{u\} )$. Every $v_{i}\in N(u)-V_{2}$ is adjacent to u and at a distance at most 2 from $v_{j_{r+1}}$. Every $v_{i}\in V_{1}^{''}$ is adjacent to $v_{j_{i}}$ and at a distance 2 from u. Hence S is a (1, 2)-dominating set and so $\gamma _{1, 2}(G) \le k+1$.

A wounded spider is the graph formed by subdividing at most $n-1$ of the edges of a star $K_{1,n}$ for $n\ge 2$. Let $WS_{n,t}$ denote the wounded spider formed by subdividing t edges of $K_{1, n}$, $1\le t \le n-1$.

Corollary 2

$\gamma _{1, 2}(WS_{n,t}) = t + 1$.

Proof

Let $V[WS_{n,t}]=\{u, v_{1}, v_{2},...,v_{n}, v^{'}_{1}, v^{'}_{2}, ... , v^{'}_{t}\}$ and $E[WS_{n,t}]=\{uv_{j}, v_{i}v^{'}_{i}|$ $1\le j \le n, 1\le i \le t\}$. Let S be any (1, 2)-dominating set of $WS_{n, t}$. For $1 \le i \le t$, to dominate $v_{i}$, either $v_{i} \in S$ or $v^{'}_{i} \in S$. Moreover, for $t + 1 \le j \le n$, to dominate $v_{j}, ~either ~u \in S~ or ~v_{j}\in S$. Therefore, $|S|\ge t+1$.

Note that $t = n - \Delta - 1$. When $t\ge 2$, then $\Delta (WS_{n,t}) \le n-3$; and by Theorem 7, $\gamma _{1, 2}(WS_{n,t}) \le t + 1$. Hence $\gamma _{1, 2}(WS_{n,t}) = t + 1$.

When $t = 1$, then $\Delta (WS_{n,t}) \ge n - 2$; and by Theorem 1, $\gamma _{1, 2}(WS_{n,t}) = 2$.

3 Composition of Two Graphs

Theorem 3

Let G be a non-trivial connected graph. Then for any graph H, $\gamma _{1, 2}(GoH) = |V(G)|$.

Proof

Let $V(G) = \{v_{1}, v_{2},..., v_{n}\}$ and $V(H) = \{u_{1}, u_{2},..., u_{s}\}$. Let $H_{1}, H_{2},..., H_{n}$ denote the copies of H, where every vertex of $H_{i}$ is adjacent to $v_{i}$, $1 \le i \le n$. Let $V(H_{i}) = \{ u^{i}_{1}, u^{i}_{2},..., u^{i}_{s}\}$. Let S be any (1, 2)-dominating set of GoH. Since there is no adjacency between the vertices in $H_{i}$ and $H_{j}$ for $i\ne j$, every $u^{i}_{r}$ in $H_{i}$ is adjacent to either $v_{i}$ or $u^{i}_{k}$, where $u^{i}_{k} \in N[u^{i}_{r}]$. Hence for each i, $1 \le i \le n$, to dominate $V(H_{i})$, we need at least one vertex in S. Hence $\gamma _{1, 2}(GoH) \ge n$. Let $S_{1} = \{v_{1}, v_{2},..., v_{n}\}$. For every $u^{i}_{r}, 1\le i \le n, 1\le r \le s, d_{GoH}(u^{i}_{r}, v_{i}) = 1~ and ~d_{GoH}(u^{i}_{r}, v_{j}) = 2$ for every $v_{j} \in N_{G}(v_{i})$. Hence $S_{1}$ is a (1, 2)-dominating set and so $\gamma _{1, 2} (GoH) = n$.

Corollary 3

Let G be any graph having t isolates. Then for any graph H, $\gamma _{1, 2}(GoH) = |V(G)| + t$, where $t\ge 0$.

Proof

Let $G_{1}, G_{2},..., G_{k}$ be the components of G.

Then $\gamma _{1, 2}(GoH) = \sum ^{k}_{i = 1}\gamma _{1, 2}(G_{i}oH)$.

Case 1. $t = 0$.

Since each $G_{i}$ is connected, by Theorem 3, $\gamma _{1, 2}(G_{i}oH) = |V(G_{i})|$. Hence $\gamma _{1, 2}(GoH) = |V(G)|$.

Case 2: $t \ne 0$.

Without loss of generality, let $G_{1}, G_{2},...,G_{t}$ denote the components of order 1. Then $G_{i}oH$ has a full - degree vertex; and so by Theorem 1, $\gamma _{1, 2}(G_{i}oH) = 2$, for $1 \le i \le t$. By Theorem 3, $\gamma _{1, 2}(G_{i}oH) = |V(G_{i})|$, for $t + 1 \le i \le k$. Thus, we get the result.

4 Some Characterizations

Theorem 4

Let G be a connected graph of order $n \ge 2$. Then $\gamma _{1, 2}(G) = n$ if and only if $n = 2$.

Proof

When $G = K_{2}$, the result is obvious. Conversely, suppose that $n \ne 2$.

Claim. $\gamma _{1, 2}(G) < n$.

We prove this result by induction on n.

When $n = 3$, a set of any two vertices of G is a  (1, 2)-dominating set of G and so $\gamma _{1, 2}(G) = 2 < n$.

Assume the result for $n = k$ with $k\ge 3$.

Next, let G be a connected graph of order $n = k+1$. Let v be a vertex that is not a cut vertex in G. Then $G-v$ is connected, and of order $n-1 = k$. By the induction hypothesis, $G-v$ has a (1, 2)-dominating set S with $|S| < k$. (i.e.) $|S| \le k-1$.

Let u be a neighbour of v.

Case 1. $u \in S$.

Since G is connected, $n\ge 3$ and v is not a cut-vertex in G, u has another neighbour (say) w. Then $S \cup \{w\}$ is a (1, 2)-dominating set in G and so $\gamma _{1,2}(G)\le k < n$.

Case 2. $u \notin S$.

Since S is a (1, 2)-dominating set in $G-v$, there exists a vertex $w\in S$ that is adjacent to u. Then $S\cup \{u\}$ is a (1, 2)-dominating set in G and so $\gamma _{1, 2}(G) \le k < n$.

Thus, by induction, the result follows.

Theorem 5

Let G be a connected graph of order $n \ge 3$. Then $\gamma _{1, 2}(G) = n-1$ iff $n = 3$. i.e. $\gamma _{1, 2}(G) = n-1$ iff $G = P_{3} ~or ~K_{3}$.

Proof

When $n = 3$, a set of any two vertices of G is a (1, 2)-dominating set of G and so $\gamma _{1, 2}(G) = 2 = n-1$. Conversely, suppose that $n\ne 3$.

Claim. $\gamma _{1, 2}(G) < n -1$.

We shall prove this result by induction on n.

When $n = 4$, since G is connected, $\Delta (G) \ge 2$. Now, any two adjacent vertices form a (1, 2)-dominating set and so $\gamma _{1, 2}(G) = 2 < n-1$.

Assume the result for $n = k$ with $k\ge 4$.

Next, let G be a connected graph of order $n = k+1$. The rest of the proof is similar to the proof of Theorem 4.

Corollary 4

Let G be any graph of order n. Then

• (i) $\gamma _{1, 2}(G) = n$ iff $G = sK_{1} \cup \frac{n - s}{2} K_{2}$, with $0\le s\le n$.

• (ii) $\gamma _{1, 2}(G) = n - 1$ iff $G = sK_{1} \cup \frac{n - s - 3}{2} K_{2} \cup H$, where $H \cong P_{3} ~or ~K_{3}$, with $0\le s \le n - 3$.

Theorem 6

Let G be a connected graph of order $n \ge 4$. Then $\gamma _{1, 2}(G) = n-2$ iff $G = P_{5}$ or G is of order 4.

Proof

If $G = P_{5}$ or G is of order 4, it is easy to verify that $\gamma _{1, 2}(G) = n-2$. Conversely, suppose that

$$\begin{aligned} \gamma _{1, 2}(G) = n-2. \end{aligned}$$

(1)

Let $n = 5$. If $\Delta (G) \ge 3 (= n -2)$, then $\gamma _{1, 2}(G) = 2$ (by Theorem  1), contradicting (1). If $\Delta (G) = 2$, then G is either $P_{5}$ or $C_{5}$; but $\gamma _{1, 2}(C_{5}) = 2$, and so $G = P_{5}$. Now, let $n\ge 6$.

Claim. $\gamma _{1, 2}(G) < n - 2$.

We shall prove this result by induction on n.

When $n = 6$, if $\Delta (G) \ge n-2$, then $\gamma _{1, 2}(G) = 2$ (by Theorem 1); if $3 \le \Delta (G) \le n - 3$, then $\gamma _{1, 2}(G) \le n - 3$ (by Theorem 7); if $\Delta (G) = 2$, then G is either $P_{6}$ or $C_{6}$ and $\gamma _{1, 2}(G) \le 3$; and in all these cases, we get a contradiction to (1).

Assume the result for $n = k$ with $k\ge 6$. Next, let G be a connected graph of order $n = k+1$. The rest of the proof is similar to the proof of Theorem 4.

Corollary 5

For any graph G of order n, $\gamma _{1, 2}(G) = n-2$ iff G is one of the following graphs:

• (i) $G = sK_{1} \cup \frac{n - 6 -s}{2} K_{2} \cup H$, where $H= 2P_{3}, 2K_{3} ~or ~P_{3} \cup K_{3}$, with $0 \le s \le n - 6$.

• (ii) $G = sK_{1}\cup P_{5}\cup \frac{n - 5 - s}{2}K_{2}$, with $0 \le s \le n - 5$.

• (ii) $G = sK_{1} \cup \frac{n -4 - s}{2} K_{2} \cup H$ where H is a connected graph of order 4, with $0\le s \le n - 4$.

5 Trees

Theorem 7

Let T be a tree of order $n \ge 2$. Then $\gamma _{1,2}(T) = 2$ if and only if T is a Star or Double Star.

Proof

Suppose that $\gamma _{1,2}(T) = 2$. Let $S = \{u, v\}$ be a (1, 2)-dominating set of T. Then every vertex in T is adjacent with either u or v. Hence $V(T) = N[u] \cup N[v]$. Then for every $x\in N(u)$ and $y\in V(T)$, $d(x, y) \le d(x, u) + d(u, y) \le 3$; similarly, for every $x\in N(v)$ and $y\in V(T)$, $d(x, y) \le 3$; for every $x\in V-\{u, v\}$, $d(u, x) + d(x, v) \le 3$; and so $d(u, v)\le 3$. Hence $diam(T) \le 3$; and so T is a Star or a Double Star $D_{r, ~s}$ (where $r + s = n-2$). Converse is obvious.

Theorem 7 deals with the trees of diameter 2 and 3. The next result deals with trees of diameter $\ge$ 4.

Theorem 8

Let T be a tree of order n with r pendant vertices. Then

• (i)  $3\le \gamma _{1, 2}(T)\le n - r$, if $diam(T)\ge 5$

• (ii)  $\gamma _{1, 2}(T) = n-r$, if $diam(T) = 3 ~or ~4$.

Proof

Let $diam(T)\ge 3$. Let $V_{1}$ denote the set of all pendant vertices in T. Then $|V - V_{1}| \ge 2$ and $V - V_{1}$ is a (1, 2)-dominating set; and so

$$\begin{aligned} \gamma _{1, 2}(T) \le n - r. \end{aligned}$$

(2)

Using Theorem 7, $\gamma _{1,2}(T)\ge 3$; and so (i) follows.

When $diam(T) = 3$, T is a double star; and by Theorem 7, $\gamma _{1, 2}(T) = 2 = n-r$. When $diam(T) = 4$, $diam(T - V_{1}) = 2$; and so $T - V_{1}$ is $K_{1, ~n - r - 1}$, where $n - r - 1\ge 2$. Let $V(K_{1, ~n - r -1}) = \{u, u_{1}, u_{2},...,u_{n - r- 1}\}$. For $1 \le j\le d_{T}(u_{i})-1$, let $v_{i_{j}}$ denote a pendant vertex adjacent to $u_{i}$. For $1\le t \le d_{T}(u) - n - r - 1$, let $w_{t}$ denote a pendant vertex adjacent to u. (If $d_{T}(u) = n - r - 1$, then there is no $w_{t}$’s).

By (2), $\gamma _{1, 2}(T) \le n - r$. Assume the contrary that $\gamma _{1, 2}(T) \ne n - r$. Then there is a (1, 2)-dominating set $S_{1}$ of cardinality $n - r - 1$.

If $S_{1} = \{u_{1}, u_{2}, ..., u_{n - r -1}\}$, then there is no vertex at a distance 2 from $v_{i_{j}}$, for $1 \le i \le n - r - 1$ and $1 \le j\le d_{T}(u_{i})-1$, which is a contradiction.

Then $u_{i} \notin S_{1}$, for some i, $1 \le i \le n - r - 1$. Without loss of generality, let $u_{1}, u_{2}, ..., u_{k} \notin S_{1}$ and $u_{k + 1}, u_{k + 2}, ..., u_{n - r - 1} \in S_{1}$, where $1 \le k \le n - r -1$. For $1 \le i \le k$, $u_{i} \notin S_{1}$; and so all $v_{i_{j}}$’s must lie in $S_{1}$. But $|S_{1}| = n - r - 1$. Hence it follows that, $d(u_{i}) = 2$ for $i = 1, 2, 3,...,k$, and $S_{1} = \{v_{1_{1}}, v_{2_{1}},..., v_{k_{1}},u_{k + 1}, u_{k + 2},...,u_{n - r -1}\}$.

Case 1. $k = n -r - 1$.

Now $S_{1} = \{ v_{1_{1}}, v_{2_{1}}, ...,v_{(n - r - 1)_{1}}\}$; and so u is not (1, 2)-dominated by $S_{1}$, a contradiction.

Case 2. $k < n -r - 1$.

Now there is no vertex in $S_{1}$ at a distance at most 2 from $v_{s_{j}}$, $k + 1 \le s \le n - r - 1$, a contradiction.

Hence $\gamma _{1, 2}(T) = n - r$.