Outer-2-independent domination in graphs

Abstract

We initiate the study of outer-2-independent domination in graphs. An outer-2-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)∖D has a neighbor in D and the maximum vertex degree of the subgraph induced by V(G)∖D is at most one. The outer-2-independent domination number of a graph G is the minimum cardinality of an outer-2-independent dominating set of G. We show that if a graph has minimum degree at least two, then its outer-2-independent domination number equals the number of vertices minus the 2-independence number. Then we investigate the outer-2-independent domination in graphs with minimum degree one. We also prove the Vizing-type conjecture for outer-2-independent domination and disprove the Vizing-type conjecture for outer-connected domination.

1 Introduction

Let G = (V, E) be a graph. We denote the number of vertices of G by n and the number of edges by m. Thus |V(G) | = n and |E(G) | = m. By complement of G (denoted by $\bar {G}$), we mean a graph which has the same vertices as G, and the two vertices of $\bar {G}$ are adjacent if and only if they are not adjacent in G. By the neighborhood of a vertex v of G, we mean the set N _G (v) = {u ∈V(G): u v ∈E(G)}. The degree of a vertex v, denoted by d _G (v), is the cardinality of its neighborhood. By a leaf we mean a vertex of degree one, while a support vertex is a vertex adjacent to a leaf. We denote the set of leaves of a graph G by L(G). Let δ(G) (Δ(G), respectively) mean the minimum (maximum, respectively) degree among all vertices of G. We denote the complete graph on n vertices by K _n . We denote the path (cycle, respectively) on n vertices by P _n (C _n , respectively). A wheel W _n , where n ≥ 4, is a graph with n vertices, formed by connecting a vertex to all vertices of a cycle C _n−1. The distance between two vertices of a graph is the number of edges in a shortest path connecting them. The eccentricity of a vertex is the greatest distance between it and any other vertex. The diameter of a graph G, denoted by diam (G), is the maximum eccentricity among all vertices of G. By K _p,q , we denote a complete bipartite graph, the partite sets of which have cardinalities p and q. Generally, let $K_{t_{1},t_{2},\dots ,t_{k}}$ denote the complete multipartite graph with vertex set S ₁ ∪ S ₂ ∪ ⋯ ∪ S _k , where |S _i | = t _i for positive integers i≤k. By a star we mean the graph K _1,m where m≥2. We say that a subset of V(G) is independent if there is no edge between any two vertices of this set. Generally, for positive integers k, a subset S of V(G) is k-independent if the maximum degree of the subgraph induced by the vertices of S is at most k−1. The k-independence number of a graph G, denoted by α ^k(G), is the maximum cardinality of a k-independent subset of the set of vertices of G. The clique number of G, denoted by ω(G), is the number of vertices of a greatest complete graph which is a subgraph of G. By G ^∗ we denote the graph obtained from G by removing all isolated vertices, leaves and support vertices. The cartesian product of graphs G and H, denoted by $G \Box H$, is a graph such that $V(G \Box H) = V(G) \times V(H)$ and $E(G \Box H) = \{(u_{1},v_{1})(u_{2},v_{2}) \colon u_{1} = u_{2}$ and v ₁ v ₂∈E(H) or v ₁ = v ₂ and u ₁ u ₂∈E(G)}.

A subset D $\subseteq$ V(G) is a dominating set of G if every vertex of V(G) ∖D has a neighbor in D, while it is an outer-connected dominating set of G, if additionally, either D = V(G) or G – D is connected. The domination (outer-connected domination, respectively) number of a graph G, denoted by γ(G) ($\tilde {\gamma }_{c}$, respectively), is the minimum cardinality of a dominating (outer-connected dominating, respectively) set of G. Outer-connected domination was introduced by Cyman [1], and further studied, for example, in [2; 4]. For a comprehensive survey of domination in graphs, see [3].

A subset D $\subseteq$ V(G) is an outer-2-independent dominating set, abbreviated O2IDS, of G if D is dominating and Δ(G −D) ≤ 1. The outer-2-independent domination number of G, denoted by $\tilde {\gamma }_{2i}(G)$, is the minimum cardinality of an outer-2-independent dominating set of G. An outer-2-independent dominating set of G of minimum cardinality is called a $\tilde {\gamma }_{2i}(G)$-set.

We initiate the study of outer-2-independent domination in graphs. We show that if a graph has minimum degree at least two, then its outer-2-independent domination number equals the number of vertices minus the 2-independence number. Then we investigate the outer-2-independent domination in graphs with minimum degree one. We find the outer-2-independent domination numbers for several classes of graphs. Next we study the influence of removing or adding vertices and edges. Then we prove some lower and upper bounds, and we characterize the extremal graphs. We also give Nordhaus–Gaddum type inequalities. We prove the Vizing-type conjecture for outer-2-independent domination. We also disprove the Vizing-type conjecture for outer-connected domination.

2 General graphs

We begin with the following straightforward observation.

Observation 1.

For every graph G, $\tilde {\gamma }_{2i}(G) \ge \gamma (G)$.

Let us observe that for any non-negative integer there exists a graph such that the difference between its outer-2-independent domination and domination numbers equals that non-negative integer.

Observation 2.

For every integer n≥3, $\tilde {\gamma }_{2i}(K_{n}) = n-2 = \gamma (K_{n})+n-3$.

We now give the outer-2-independent domination numbers of paths and cycles.

Observation 3.

For every integer n≥3, $\tilde {\gamma }_{2i}(P_{n}) = \tilde {\gamma }_{2i}(C_{n}) = \lfloor (n+2)/3 \rfloor$.

We now give the outer-2-independent domination numbers of complete multipartite graphs.

PROPOSITION 4

Let n ₁≤n ₂≤⋯≤n _t (where t≥3) be positive integers. We have

$$\tilde{\gamma}_{2i}(K_{n_{1},n_{2},\hdots,n_{t}}) = \left\{\begin{array}{l} \sum\limits_{j=1}^{t-1} n_{j} \textnormal{ if } n_{t} \ge 2; \\ t-2 \textnormal{ if } n_{t} = 1. \end{array}\right. $$

Proof.

Let V ₁, V ₂, … , V _t be the partite sets of the graph $K_{n_{1},n_{2},\hdots ,n_{t}}$, where |V _i | = n _i . If n _t = 1, then n _i = 1 for 1 ≤i ≤t. Thus G is a complete graph K _t and $\tilde {\gamma }_{2i}$(G) = t − 2. Let n _t ≥ 2. If one vertex from partite 1 to partite t − 1 is not in an O2IDS, then this vertex with the vertices of partite t induce a subgraph with Δ≥2. Thus all vertices from partite 1 to partite t − 1 must be in any O2IDS. Now if we say S consists of the vertices of 1 to t − 1 partite sets, then S has minimum cardinality. Thus $\tilde {\gamma }_{2i}(K_{n_{1},n_{2},\cdots ,n_{t}}) = {\sum }_{j=1}^{t-1} n_{j}$. □

We have the following lower bound on the outer-2-independent domination number of a graph in terms of its clique number.

Observation 5.

For every graph G, $\tilde {\gamma }_{2i}(G) \ge \omega (G)-2$.

Let us observe that the above bound is tight. For n≥3 we have $\tilde {\gamma }_{2i}(K_{n}) = n-2 = \omega (K_{n})-2$.

Now, let us observe that for any non-negative integer there exists a graph such that the difference between its outer-2-independent domination number and clique number equals the non-negative integer.

Observation 6.

For every positive integer k, $\tilde {\gamma }_{2i}(P_{3k}) = \omega (P_{3k})+k-2$.

We now prove that if a graph has no leaves and isolated vertices, then its outer-2-independent domination number equals the number of vertices minus the 2-independence number.

PROPOSITION 7

Let G be a graph. If δ(G)≥2, then $\tilde {\gamma }_{2i}(G) = n-\alpha ^{2}(G)$.

Proof.

Let D be a maximum 2-independent set of G. Every vertex of D has at most one neighbor in the set D. Since δ(G)≥2, every vertex of D has a neighbor in V(G) ∖D. Let us observe that V(G) ∖D is a dominating set of the graph G. Consequently, it is an outer-2-independent dominating set of G. Therefore $\tilde {\gamma }_{2i}(G) \le n-\alpha ^{2}(G)$. On the other hand, we have $\alpha ^{2}(G) \ge n-\tilde {\gamma }_{2i}(G)$ as the complement of every outer-2-independent dominating set is a 2-independent set. □

3 Graphs with minimum degree one

Throughout this section we only consider connected graphs with minimum degree one.

We have the following relation between the outer-2-independent domination number of a graph and the 2-independence number of the graph obtained from it by removing all leaves and support vertices.

Lemma 8.

For every graph G≠K ₂ with l leaves, $\tilde {\gamma }_{2i}(G) = n-\alpha ^{2}(G^{*})-l$.

Proof.

Let us observe that there exists a $\tilde {\gamma }_{2i}(G)$-set that does not contain any leaf. Let D be such a set. We have V(G) ∖(D ∪L(G)) $\subseteq$ V(G ^∗). The set V(G) ∖(D ∪L(G)) is 2-independent, thus α ²(G ^∗) ≥ |V(G) ∖(D ∪L(G)) | = n $-\tilde {\gamma }_{2i}$(G) −l. Now let D ^∗ be a maximum 2-independent set of the graph G ^∗. Let us observe that in the graph G every vertex of D ^∗ has a neighbor in the set V(G) ∖(D ^∗ ∪L(G)). This implies that |V(G) ∖(D ^∗ ∪L(G)) | is an outer-2-independent dominating set of the graph G. Therefore $\tilde {\gamma }_{2i}$(G) ≤ |V(G) ∖(D ^∗ ∪L(G)) | = n −α ²(G ^∗) −l. This implies that $\tilde {\gamma }_{2i}$(G) = n −α ²(G ^∗) −l. □

We have the following bounds on the outer-2-independent domination number of a graph.

Observation 9.

For every graph G, $1 \le \tilde {\gamma }_{2i}(G) \le n$.

We now characterize the graphs attaining the bounds from the previous observation.

PROPOSITION 10

Let G be a graph. Then

• (i) $\tilde {\gamma }_{2i}(G) = 1$ if and only if G has a universal vertex v such that each component of G−v is K ₁ or K ₂;

• (ii) $\tilde {\gamma }_{2i}(G) = n$ if and only if $G = \overline {K_{n}}$.

Proof.

First assume that G has a universal vertex, say v, such that G−v consists of only isolated vertices and paths on two vertices. Let us observe that {v} is an outer-2-independent dominating set of the graph G, as the vertex v dominates the whole graph, and the set V(G)∖{v} is 2-independent. Thus $\tilde {\gamma }_{2i}(G) = 1$.

Now assume that G is a graph such that $\tilde {\gamma }_{2i}(G) = 1$. Let v be a vertex that forms an outer-2-independent dominating set of G. The vertex v is universal, as all vertices of G are dominated by it. The set V(G)∖{v} is 2-independent, thus G−v consists of isolated vertices and paths on two vertices.

Obviously, $\tilde {\gamma }_{2i}(\overline {K_{n}}) = n$. Now let G be any graph such that $\tilde {\gamma }_{2i}(G) = n$. Suppose that some two vertices of G, say x and y, are adjacent. Let us observe that V(G)∖{x} is an O2IDS of the graph G. Therefore $\tilde {\gamma }_{2i}(G) \le n-1$, a contradiction. This implies that G consists of isolated vertices. □

COROLLARY 11

For every graph G with at least two vertices, $\tilde {\gamma }_{2i}(G) \le n-1$.

3.1 Bounds

We have the following upper bound on the outer-2-independent domination number of a graph.

PROPOSITION 12

For every graph G with s support vertices , we have

$$\tilde{\gamma}_{2i}(G) \le \frac{\Delta(G) \cdot (n-l)+s}{\Delta(G)+1}. $$

Proof.

By Lemma 8, we have $\tilde {\gamma }_{2i}(G) = n-\alpha ^{2}(G^{*})-l$. We now get

$$\alpha^{2}(G^{*}) \ge \alpha(G^{*}) \ge \gamma(G^{*}) \ge \frac{|V(G^{*})|}{\Delta(G^{*})+1} \ge \frac{n-s-l}{\Delta(G)+1} . $$

□

We have the following upper bound on the outer-2-independent domination number of a graph in terms of its diameter.

PROPOSITION 13

If G is a graph of diameter D, then $\tilde {\gamma }_{2i}(G) \le n-\lfloor 2(d+1)/3 \rfloor$.

Proof.

Let v ₀,v ₁,…,v _d be a diametrical path in G. If d∈{3k−1,3k}, then let S={v _3i ,v _3i+2:0≤i≤(d−1)/3}. If d=3k+1, then let S={v _3i ,v _3i+2:$0 \le i \le d/3-1\} \cup \{v_{d}\}$. Let us observe that V(G)∖S is an O2IDS of the graph G. □

The bound in the previous proposition is tight, as $\tilde {\gamma }_{2i}(P_{n}) = \lfloor (n+2)/3 \rfloor = n-\lfloor 2n/3\rfloor = n-\lfloor 2(d+1)/3 \rfloor$.

We have the following bounds on the outer-2-independent domination number of a graph in terms of its order and size.

PROPOSITION 14

For every graph G,

$$n-2-\sqrt{n(n-3)-2m+5} \le \tilde{\gamma}_{2i}(G) \le n-2+\sqrt{n(n-3)-2m+5}. $$

Proof.

Let D be a $\tilde {\gamma }_{2i}(G)$-set. Let t denote the number of edges between the vertices of D and the vertices of V(G) ∖D. Obviously, m≤(n−|D|−1)/2 + t+|E(G[D])|. Since G has at least one leaf, we have t≤|D|⋅(|V(G)∖D|−1)+1. Obviously, |E(G[D])|≤|D|⋅(|D|−1)/2. Now simple calculations imply the result. □

We now study the influence of the removal of a vertex of a graph on its outer-2-independent domination number.

PROPOSITION 15

Let G be a graph. For every vertex v of G, $\tilde {\gamma }_{2i}(G)-1 \le \tilde {\gamma }_{2i}(G-~\!v)$ $\le \tilde {\gamma }_{2i}(G)+d_{G}(v)-1$.

Proof.

Let D be a $\tilde {\gamma }_{2i}(G)$-set. If v∉D, then observe that D is an O2IDS of the graph G−v. Now assume that v∈D. Let us observe that $D \cup N_{G}(v) \setminus \{v\}$ is an O2IDS of the graph G−v. Therefore $\tilde {\gamma }_{2i}(G-v) \le |D \cup N_{G}(v) \setminus \{v\}|$ $\le |D \setminus \{v\}|+|N_{G}(v)| = \tilde {\gamma }_{2i}(G)+d_{G}(v)-1$.

Now let $D^{\prime }$ be any $\tilde {\gamma }_{2i}(G-v)$-set. It is easy to see that $D^{\prime } \cup \{v\}$ is an O2IDS of the graph G. Thus $\tilde {\gamma }_{2i}(G) \le \tilde {\gamma }_{2i}(G-v)+1$. □

Let us observe that the bounds from the previous proposition are tight. For the lower bound, let G = K _n , where n≥4. We have $\tilde {\gamma }_{2i}(K_{n}) = n-2 = n$ $-3+1 = \tilde {\gamma }_{2i}(K_{n-1})+1 = \tilde {\gamma }_{2i}(K_{n}-v)+1$. For the upper bound, let G be a star K _1,m . We denote the central vertex by v. We have G−v = m K ₁. We get $\tilde {\gamma }_{2i}(G-v) = \tilde {\gamma }_{2i}(mK_{1}) = m = 1+m-1 = \tilde {\gamma }_{2i}(G)+d_{G}(v)-1$.

We now study the influence of the removal of an edge of a graph on its outer-2-independent domination number.

PROPOSITION 16

Let G be a graph. For every edge e> of G,

$$\tilde{\gamma}_{2i}(G-e) \in \{\tilde{\gamma}_{2i}(G)-1,\tilde{\gamma}_{2i}(G),\tilde{\gamma}_{2i}(G)+1\} . $$

Proof.

Let D be a $\tilde {\gamma }_{2i}(G)$-set, and let e = x y be an edge of G. If x,y∉D or x,y∈D, then it is easy to observe that D is an O2IDS of the graph G−e. Now assume that exactly one of those vertices, say x, belongs to the set D. Let us observe that $D \cup \{y\}$ is an O2IDS of G−e. Thus $\tilde {\gamma }_{2i}(G-e) \le \tilde {\gamma }_{2i}(G)+1$. Now let $D^{\prime }$ be a $\tilde {\gamma }_{2i}(G-e)$-set. If some of the vertices x and y belong to the set $D^{\prime }$, then $D^{\prime }$ is an O2IDS of the graph G. If none of the vertices x and y belongs to the set $D^{\prime }$, then it is easy to observe that $D^{\prime } \cup \{x\}$ is an O2IDS of the graph G. Therefore $\tilde {\gamma }_{2i}(G) \le \tilde {\gamma }_{2i}(G-e)+1$. □

Let us observe that all values from the previous proposition can be achieved. For the lowest value, let G be a graph obtained from K ₄ by removing an edge. Let e be an edge of G such that G−e≠C ₄. We have $\tilde {\gamma }_{2i}(G-e) = 1 = \tilde {\gamma }_{2i}(G)-1$. For the middle value, let e be an edge of K ₃. We have $\tilde {\gamma }_{2i}(G-e) = 1 = \tilde {\gamma }_{2i}(G)$. For the highest value, let e be the edge of K ₂. We have $\tilde {\gamma }_{2i}(G-e) = 2 = \tilde {\gamma }_{2i}(G)+1$.

Similarly, we have the following proposition concerning the influence of adding an edge on the outer-2-independent domination number of a graph.

PROPOSITION 17

Let G be a graph. If e∉E(G), then

$$\tilde{\gamma}_{2i}(G+e) \in \{\tilde{\gamma}_{2i}(G)-1,\tilde{\gamma}_{2i}(G)\textnormal{,}\,\tilde{\gamma}_{2i}(G)+1\}. $$

3.2 Nordhaus–Gaddum type inequalities

We now give Nordhaus–Gaddum type inequalities for the sum of the outer-2-independent domination number of a graph and its complement.

Theorem 18.

For every graph G, $n-2 \le \tilde {\gamma }_{2i}(G)+\tilde {\gamma }_{2i}(\bar {G}) \le 2n$ , with equality in the upper bound if and only if G=K ₁.

Proof.

Obviously, $\tilde {\gamma }_{2i}(G) \le n$ and $\tilde {\gamma }_{2i}(\bar {G}) \le n$. Thus $\tilde {\gamma }_{2i}(G)+\tilde {\gamma }_{2i}(\bar {G}) \le 2n$. Now assume that $\tilde {\gamma }_{2i}(G) \le n-3$. Let D be a $\tilde {\gamma }_{2i}(G)$-set. Let us observe that for any triple vertices of V(G) ∖D, at least one of them is adjacent in the graph $\bar {G}$ to both the two remaining ones. Let $\bar {D}$ be a $\tilde {\gamma }_{2i}(\bar {G})$-set. At most two vertices of every triple of vertices of V(G) ∖D do not belong to the set $\bar {D}$ as its complement is 2-independent. This implies that at most two vertices of V(G) ∖D do not belong to the set $\bar {D}$. Therefore $|\bar {D}| \ge |V(G) \setminus D|-2$. We now get $\tilde {\gamma }_{2i}(G)+\tilde {\gamma }_{2i}(\bar {G}) = |D|+|\bar {D}| \ge |D|+|V(G) \setminus D|-2 = n-2$.

Assume that $\tilde {\gamma }_{2i}(G)+\tilde {\gamma }_{2i}(\bar {G}) = 2n$. Then $\tilde {\gamma }_{2i}(G) = \tilde {\gamma }_{2i}(\bar {G}) = n$, and by Proposition 10, $G = \bar {G} = \overline {K_{n}}$. This is only possible if n=1, and so G = K ₁. □

We also characterize graphs G such that $\tilde {\gamma }_{2i}(G)+\tilde {\gamma }_{2i}(\bar {G}) = 2n-1$.

PROPOSITION 19

If G is a connected graph, then $\tilde {\gamma }_{2i}(G)+\tilde {\gamma }_{2i}(\bar {G}) = 2n-1$ if and only if G = K ₂.

Proof.

We have $\tilde {\gamma }_{2i}(K_{2})+\tilde {\gamma }_{2i}(\overline {K_{2}}) = 2+1 = 3 = 2n-1$. Now assume that for some graph G we have $\tilde {\gamma }_{2i}(G)+\tilde {\gamma }_{2i}(\bar {G}) = 2n-1$. This implies that $\tilde {\gamma }_{2i}(G) = n$ or $\tilde {\gamma }_{2i}(\bar {G}) = n$. Without loss of generality, we assume that $\tilde {\gamma }_{2i}(G) = n$. By Proposition 10, we have $G = \overline {K_{n}}$ and so $\bar {G}$ is a complete graph. Observation 2 implies that $\bar {G} = K_{2}$. □

4 Cartesian product of graphs

In this section we investigate the outer-2-independent domination and outer-connected domination for Cartesian product of graphs. We also solve Vizing-type conjectures for those two variants of domination.

4.1 Outer-2-independent domination for Cartesian product of graphs

First we consider the Cartesian product of two cycles.

Theorem 20.

For any positive integers m and n, $\tilde {\gamma }_{2i}(C_{m} \Box C_{n}) = \lceil mn/2 \rceil$.

Proof.

Proposition 7 implies that $\tilde {\gamma }_{2i}$($C_{m} \Box C_{n}$) = m n−α ²($C_{m} \Box C_{n}$). Let V($C_{m} \Box C_{n}$) = { v _{i j} : 1 ≤i ≤m and 1 ≤j ≤n}, where v _{i j} is the vertex in row i and column j, and it is adjacent to vertices v _i−1j , v _i+1j , v _{i j−1}, v _{i j+1} (where m + 1 for rows means 1, and n + 1 for columns means 1). Let S be a maximum 2-independent set of $C_{m} \Box C_{n}$. Let us observe that the graph G[S] has at most one of edges v _{i j} v _{i j+1}, v _{i j} v _{i j−1}, v _{i j} v _i−1j , v _{i j} v _i+1j . Also, if two vertices v _{i j} and v _{i j+1} belong to the set S, then none of the vertices v _i+1j , v _i+1j+1, v _i−1j , v _i−1j+1, v _{i j−1}, v _{i j+2} belongs to S. First assume that m or n is even. Without loss of generality, we assume that m = 2k. For each column, at most k vertices can be in S, thus |S| ≤n ⋅k = m n/2. Let S = { v ₁₁, v ₃₁, … , v _m−11, v ₂₂, v ₄₂, … , v _m2, v ₁₃, v ₃₃, … , v _m−13, … , v _2n , v _4n , … , v _{m n} }. Let us observe that the set S is 2-independent. We have |S| = m n/2. This implies that α ²(S) = m n/2 = ⌊m n/2⌋. Now assume that both m and n are odd. Let m = 2k+1 and n = 2l+1. Let us observe that for any two adjacent columns, at most 2k+1 vertices belong to the set S. Thus |S| ≤ ⌊(2k+1)(2l+1)/2⌋ = ⌊m n/2⌋. Let S = { v ₁₂, v ₁₄, … , v _1n−1, v ₂₁, v ₂₃, … , v _2n , v ₃₂, v ₃₄, … , v _3n−1, v _m−11, v _m−13, … , v _m−1n , v _m2, v _m4, … , v _{m n−1}}. Let us observe that the set S is 2-independent. We have |S | = (m n−1) /2 = ⌊m n/2⌋. This implies that α ²(S) = ⌊m n/2⌋. We now get $\tilde {\gamma }_{2i}$($C_{m} \Box C_{n}$) = m n−α ²($C_{m} \Box C_{n}$) = m n−⌊m n/2⌋ = ⌈m n/2⌉. □

Similarly we obtain the following results.

Theorem 21.

For any positive integers m and n, $\tilde {\gamma }_{2i}(P_{m} \Box C_{n}) = \lfloor mn/2 \rfloor$.

Theorem 22.

For any positive integers m and n with m or n even we have $\tilde {\gamma }_{2i}(P_{m} \Box P_{n})= \lfloor mn/2 \rfloor$ . Also, if m,n≤3, then $\tilde {\gamma }_{2i}(P_{m} \Box P_{n})= \lfloor mn/2 \rfloor$.

Theorem 23.

Let m≥3 and n≥3 be positive odd integers. Then $\tilde {\gamma }_{2i}(P_{m} \Box P_{n})$ =⌊mn/2⌋−⌊(n+1)/6⌋.

Proof.

Let m=2t+1. If 3k−1≤n≤3k+3 for even positive integers k, then ⌊(n+1)/6⌋ = k/2. Thus without loss of generality we can assume that n∈{3k−1,3k+1,3k+3} for an even k≥2.

Let n=3k−1 and v _{i j} be the vertex in i-th row and j-th column of $P_{m} \Box P_{n}$. The set {v _{i j} :i is odd, 1≤i≤2t+1 and $j \in \{1,2,4,5,\hdots ,3k-2,3k-1\}\} \bigcup \{v_{ij} \colon i$ is even, 2≤i≤2t and j∈{3,6,…,3k−3}} is a maximum 2-independent set of $P_{n} \Box P_{m}$. Therefore $\alpha ^{2}(P_{m} \Box P_{n}) = (t+1) \cdot 2k+t(k-1) = t(3k-1)+2k$ and $\tilde {\gamma }_{2i}(P_{m} \Box P_{n}) = t(3k-1)+k-1$. It is easy to see that t(3k−1) + k−1=⌊(2t+1)(3k−1)/2⌋−k/2. Thus $\tilde {\gamma }_{2i}(P_{m} \Box P_{n}) = \lfloor mn/2 \rfloor -\lfloor (n+1)/6 \rfloor$.

Let n=3k+1. The set {v _{i j} :i is odd and $j \in \{1,2,4,5,\hdots ,3k-2,3k-1,3k+1\}\} \bigcup \{v_{ij} \colon i\; \text {is even and}\; j \in \{3,6,\hdots ,3k-3,3k\}\}$ is a maximum 2-independent set of $P_{n} \Box P_{m}$. Similar calculation shows that $\tilde {\gamma }_{2i}(P_{m} \Box P_{n})= \lfloor mn/2 \rfloor -\lfloor (n+1)/6 \rfloor$.

Let n=3k+3. The set $\{v_{ij} \colon i \;\text { is odd and }\; j \in \{1,2,4,5,\hdots ,3k+1,3k+2\}\} \bigcup \{v_{ij} \colon i \;\text { is even and }\; j \in \{3,6,\hdots ,3k,3k+3\}\}$ is a maximum 2-independent set of $P_{n} \Box P_{m}$. Also it is easily seen that $\tilde {\gamma }_{2i}(P_{m} \Box P_{n}) = \lfloor mn/2 \rfloor -\lfloor (n+1)/6 \rfloor$. □

We now consider the Cartesian product of a path and a complete graph.

Theorem 24.

Let m and n≥4 be positive integers. We have $\tilde {\gamma }_{2i}(P_{m} \Box K_{n})$ = m(n−2).

Proof.

Proposition 7 implies that $\tilde {\gamma }_{2i}(P_{m} \Box K_{n}) = mn-\alpha ^{2}(P_{m} \Box K_{n})$. Let $V(P_{m} \Box K_{n})$ ={v _{i j} :1≤i≤m and 1≤j≤n}, where v _{i j} is the vertex in row i and column j. Let S be a maximum 2-independent set of the graph $P_{m} \Box K_{n}$. Let us observe that S contains at most two vertices from every row. Thus $\alpha ^{2}(P_{m} \Box K_{n}) \le 2m$. Now let S consist of two first vertices of every odd row and two last vertices of every even row. Let us observe that the set S is 2-independent. We have |S|=2m. This implies that $\alpha ^{2}(P_{m} \Box K_{n}) = 2m$. We now get $\tilde {\gamma }_{2i}(P_{m} \Box K_{n})$ $= mn-\alpha ^{2}(P_{m} \Box K_{n}) = mn-2m = m(n-2)$. □

We now consider the Cartesian product of a cycle and a complete graph.

Theorem 25.

If m is an odd integer, then $\tilde {\gamma }_{2i}(C_{m} \Box K_{4}) = 2m+2$ and $\tilde {\gamma }_{2i}(C_{m} \Box K_{5})$ =3m+1. Now let m≥4 and n≥4 be any integers. We have $\tilde {\gamma }_{2i}(C_{m} \Box K_{n}) = m(n-2)$ if m is even or n≥6.

Proof.

Proposition 7 implies that $\tilde {\gamma }_{2i}(C_{m} \Box K_{n}) = mn-\alpha ^{2}(C_{m} \Box K_{n})$. Let V(C _m $\Box K_{n}) = \{v_{ij} \colon 1 \le i \le m \;\text { and }\; 1 \le j \le n\}$, where v _{i j} is the vertex in row i and column j. Let S be a maximum 2-independent set of the graph $C_{m} \Box K_{n}$. Let us observe that S has at most 2m vertices. Thus $\alpha ^{2}(C_{m} \Box K_{n}) \le 2m$. If m is even, then let S consist of two first vertices of every odd column and two last vertices of every even column. Let us observe that the set S is 2-independent. Now assume that m is odd and n is at least six. Let S differ from the above defined S only in that from the last column it contains the third and the fourth vertex instead of the first two vertices. Let us observe that the set S is 2-independent. We have |S|=2m. This implies that $\alpha ^{2}(C_{m} \Box K_{n}) = 2m$. We now get $\tilde {\gamma }_{2i}(C_{m} \Box K_{n}) = mn-\alpha ^{2}(C_{m} \Box K_{n}) = mn-2m = m(n-2)$. □

4.2 Vizing-type conjecture for outer-2-independent domination

We now prove that the Vizing-type conjecture for the outer-2-independent domination is true.

Theorem 26.

For any graphs G and H, $\tilde {\gamma }_{2i}(G \Box H) \ge \tilde {\gamma }_{2i}(G) \cdot \tilde {\gamma }_{2i}(H)$.

Proof.

We consider $G \Box H$ in a matrix form, where we have |V(G)| rows H and |V(H)| columns G. Proposition 7 implies that $\tilde {\gamma }_{2i}(G \Box H) = |V(G)| \cdot |V(H)|$ $-\alpha ^{2}(G \Box H)$. Let S be any minimum 2-independent set of the graph $G \Box H$. Let us observe that the vertices of any column, which belong to the set S, form a 2-independent set of the graph G. Therefore $\alpha ^{2}(G \Box H) \le |V(H)| \cdot \alpha ^{2}(G)$. We now get

$$\begin{array}{lll} \tilde{\gamma}_{2i}(G \Box H) & = & |V(G)||V(H)|-\alpha^{2}(G \Box H) \ge |V(G)||V(H)|-|V(H)|\alpha^{2}(G) \\ & \ge & |V(G)||V(H)|-|V(H)|\alpha^{2}(G)+\alpha^{2}(H)(\alpha^{2}(G)-|V(G)|) \\ & = & |V(G)||V(H)|-|V(H)| \cdot \alpha^{2}(G)+\alpha^{2}(H)\alpha^{2}(G)-\alpha^{2}(H)|V(G)| \\ & = & (|V(G)|-\alpha^{2}(G))(|V(H)|-\alpha^{2}(H)) = \tilde{\gamma}_{2i}(G) \cdot \tilde{\gamma}_{2i}(H) . \end{array} $$

□

We have the following corollary from results of the previous subsection.

COROLLARY 27

For certain positive integers m and n, we have

• $\tilde {\gamma }_{2i}(C_{m} \Box C_{n})> \tilde {\gamma }_{2i}(C_{m}) \tilde {\gamma }_{2i}(C_{n})$,

• $\tilde {\gamma }_{2i}(P_{m} \Box P_{n})> \tilde {\gamma }_{2i}(P_{m}) \tilde {\gamma }_{2i}(P_{n})$,

• $\tilde {\gamma }_{2i}(P_{m} \Box C_{n})> \tilde {\gamma }_{2i}(P_{m}) \tilde {\gamma }_{2i}(C_{n})$,

• $\tilde {\gamma }_{2i}(P_{m} \Box K_{n})> \tilde {\gamma }_{2i}(P_{m}) \tilde {\gamma }_{2i}(K_{n})$,

• $\tilde {\gamma }_{2i}(C_{m} \Box K_{n})> \tilde {\gamma }_{2i}(C_{m}) \tilde {\gamma }_{2i}(K_{n})$.

4.3 Vizing-type conjecture for outer-connected domination

We disprove the Vizing-type conjecture for outer-connected domination.s

Observation 28 ([1]).

For integers n≥3, $\tilde {\gamma }_{c}(C_{n}) = n-2$.

Counterexample 1.

Let G be a graph $C_{5} \Box C_{5}$ with vertex set {v _ij :1≤i,j≤5}. Let us observe that {v ₁₁ ,v ₂₃ ,v ₃₅ ,v ₄₂ ,v ₅₄ } is a minimum outer-connected dominating set of G. Thus $\tilde {\gamma }_{c}(C_{5} \Box C_{5}) = 5$ . By Observation 28, we have $\tilde {\gamma }_{c}(C_{5}) = 3$ . We now get $\tilde {\gamma }_{c}(C_{5} \Box C_{5}) = 5 < 9 = \tilde {\gamma }_{c}(C_{5}) \cdot \tilde {\gamma }_{c}(C_{5})$.