The outer-connected vertex edge domination number in Lexicographic product graphs

1. Introduction

Let \(G=(V,E)\) be a simple connected graph. The length of the shortest \(x-y\) path in \(G\) is the distance between \(x\) and \(y\) denoted by \(d(x,y)\) and \(max \{d(x,y): x,y \in V(G)\}\) is the diameter of \(G\) denoted by \(diam(G)\). Let \(P_n\), \(C_n\), \(K_n\), \(W_n\) and \(S_n\) denote the path of length \(n\), cycle of length \(n\), complete graph of length \(n\), wheel of length \(n\) and star graph of length \(n\) respectively. A subset \(D \subset V(G)\) is a dominating set (DS), of a graph \(G\) if every vertex of \(V(G) \setminus D\) has a neighbor in \(D\). The domination number of a graph \(G\), denoted by \(\gamma (G)\), is the minimum cardinality of a dominating set of \(G\), see [1]. A vertex \(v \in V(G)\) dominates an edge \(e \in E(G)\) if \(v\) is incident with \(e\) or with an edge adjacent to \(e\). The vertex-edge dominating set of \(G\) was introduced in [2] as the subset \(D \subset V(G)\) if every edge of \(G\) is vertex-edge dominated by a vertex in \(D\). The vertex-edge domination number of a graph \(G\) is the minimum cardinality of a vertex-edge dominating set of \(G\) and it is denoted by \(\gamma_{ve}(G)\). Further studies of vertex-edge domination in graphs can be found in [3, 4, 5].

A subset \(D\) of \(V(G)\) is an outer-connected dominating set of a graph \(G\) if \(D\) is a dominating set and \(G \setminus D\) is connected. In [6], the outer-connected domination number of a graph \(G\) was given as the outer-connected dominating set of \(G\) with minimum cardinality and is denoted by \(\gamma_c(G)\). Vizing [7] posed a conjecture concerning the domination number of the Cartesian product graphs. He showed that \(\gamma(G)\gamma(H) \leq \gamma(G \times H)\). For a survey of domination in Cartesian products, see [8]. In [9], the notion of outer-connected vertex edge dominating set was introduced. A subset \(D\) of \(V(G)\) is an outer-connected vertex-edge dominating set (OCVEDS) of \(G\) if \(D\) is a vertex edge dominating set of \(G\) and the graph \(G \setminus D\) is connected. The outer connected vertex-edge domination number of a graph \(G\), denoted by \(\gamma_{ve}^{oc}(G) \), is the minimum cardinality of an outer connected vertex edge dominating set of \(G\). The outer connected vertex edge domination number in Cartesian product of graphs has been given in [10].

The rest of this paper is organized as follows. In next Section 2, we give definition of lexicographic product and some known results. In Section 3, we give the outer-connected vertex edge domination number of the product \(P_m \ \circ \ H\) and \(C_m \ \circ \ H\) and the outer-connected vertex edge domination number of the product \(G \ \circ \ H\) where \(\gamma_{ve}^{oc}(G)=1\) and Section 4 contains concluding remarks.

2. Preliminaries

Definition 1. The lexicographic product \(G\circ H\) of two graphs \(G\) and \(H\) is a graph with vertex set \(V(G)\times V(H)\) in which \((x_1,y_1)\) and \((x_2,y_2)\) are adjacent if one of the following condition holds:

1. \(\{x_1,x_2\}\in E(G)\).
2. \(x_1= x_2\) and \(\{y_1,y_2\}\in E(H)\).

The graphs \(G\) and \(H\) are known as the factors of \(G\circ H\).

Suppose we are dealing with \(m\)-copies of a graph \(G\), we denote these \(m\)-copies of \(G\) by \(G^i\), where \(i=1,2,3,…,m\). The Lexicographic product \(G\circ H\), of graphs \(G\) and \(H\), can also be viewed as the graph obtained by replacing each vertex of \(G\) by a copy of \(H\) and every edge of \(G\) by the complete bipartite graph \(K_{[H],[H]}\). Henceforth, for any vertex \(i \in V(G)\), we refer the copy of \(H\), denoted by \(H^i\), in \(G \ \circ \ H\) corresponding to the vertex \(i\) as the \(i^{th}\) copy of \(H\) in \(G \ \circ \ H\). The following is the outer-connected vertex edge domination number of some standard graphs that would be used in this paper.

1. [9] \( \gamma_{ve}^{oc}(P_n)= \left\{\begin{array}{cc} 1 ,& \; if \ n=2 \ or \ 3 \\ \ \\ 2,& \; if \ n=4 \ or \ 5 \\ \ \\ n-3 ,& \; otherwise \\ \end{array}\right. \)
2. [9] \( \gamma_{ve}^{oc}(C_n)= \left\{\begin{array}{cc} 1 ,& \; if \ n=3 \ or \ 4 \\ \ \\ n-3 ,& \; otherwise \\ \end{array}\right. \)
3. [9] \( \gamma_{ve}^{oc}(K_n)=1\), for \(n \geq 1\)
4. \( \gamma_{ve}^{oc}(S_n)=1\), for \(n \geq 1\)
5. \( \gamma_{ve}^{oc}(W_n)=1\), for \(n \geq 1\)

3. Main results

In this section, we give our main results.

3.1. Outer-connected vertex edge domination number in \(P_m \ \circ \ H\) and \(C_m \ \circ \ H\)

Theorem 2. Let \(G\) be a cycle or path of order \(m\) and \(H\) be a path with maximum length four, then \(\gamma_{ve}^{oc}(G \ \circ \ H)= \lfloor \frac{m+2}{3} \rfloor\).

Proof. Let \(D=\{x_1,x_2,x_3,…,x_j\}\), \( 1 \leq j \leq \lfloor \frac{m+2}{3} \rfloor \in \gamma_{ve}^{oc}(G \ \circ \ P_n)\). The graph \(G \ \circ \ P_n\) has \(m\) copies of \(P_n\). Next we consider the following three cases.
Case 1: whenever \(m \equiv 0 (mod \ 3)\)
Let each element of \(D\) belong to any vertex of copies \(P_n^2,P_n^5,P_n^8,…,P_n^{m-1}\) respectively.
Case 2: whenever \(m \equiv 1 (mod \ 3)\)
Let each element of \(D\) belong to any vertex of copies \(P_n^2,P_n^5,P_n^8,…,P_n^{m-2}\) and \(P_n^m\) respectively.
Case 3: whenever \(m \equiv 2 (mod \ 3)\)
Again, let each element of \(D\) belong to any vertex of copies \(P_n^2,P_n^5,P_n^8,…,P_n^m\) respectively.
Clearly, for each of the cases above, each edge in \(G \ \circ \ P_n\), \(2 \leq n \leq 5\) is dominated by a vertex in \(D\) and \((G \ \circ \ P_n)\setminus D\) is connected. Hence the proof.

Next, we have the following corollary which is immediate from Theorem 2.

Corollary 3. Let \(G\) be a cycle or path of order \(m\), suppose we have a graph \(H\) such that \(\gamma_{ve}^{oc}(H)=1\), then \(\gamma_{ve}^{oc}(G \ \circ \ H)=\lfloor \frac{m+2}{3} \rfloor \).

Proof. The proof of this Corollary is same as that of Theorem 2.

Remark 1. Since the Wheel graph, Star graph, Complete graph and the Cycle of order \(3 \ or \ 4\) has their outer connected vertex edge domination number to be equal to \textit{one}, then the bound mentioned in Corollary 3 covers them.

Lemma 4. Let \(G\) be a cycle or path of order three and \(H=P_n\), \( n \geq 6\) then \(\gamma_{ve}^{oc}(G \ \circ \ P_n)=2\).

Proof. Consider the copies \(P_n^2\) and \( P_n^3\) in \(G \ \circ \ P_n\). Assume that \(D=\{x_1,x_2\} \in \{P_n^2 \cup P_n^3 \}\), where \(x_1 \in V(P_n^2)\) and \(x_2 \in V(P_n^3)\). It is easy to see that each edge in \(G \ \circ \ P_n\) is dominated by a vertex in \(D\). Also, \((G \ \circ \ P_n)\setminus D\) is connected. Therefore \(\gamma_{ve}^{oc}(G \ \circ \ P_n)=2\), and this completes Hence the proof.

Theorem 5. Let \(G\) be a cycle or path of order \(m\) and \(H=P_n, \ n\geq 6\), then
\(\gamma_{ve}^{oc}(G \ \circ \ P_n)=\left\{\begin{array}{cc} \frac{m+1}{2} ,& \; if \ m \ is \ odd \\ \ \\ \frac{m}{2},& \; if \ m \equiv 0 \ (mod \ 4) \\ \ \\ \frac{m+2}{2} ,& \; otherwise \\ \end{array}\right. \)

Proof. Let \(D\) be an OCVEDS of \(G \ \circ \ P_n\). We now consider the following three cases.
Case 1: whenever \(m \equiv \ 0 \ or \ 3 \ (mod \ 4)\)
Applying Lemma 4 to the first three copies of \(P_n\) we have \(|D|=2\). Next, for \(4 \leq q \leq m\), consider the \(q^{th}\) inner copies of \(P_n\) in the following way. Let \(D’=\{y_1,y_2\}\) such that \(y_1 \in V(P_n^q)\) if \(q \equiv \ 2 \ (mod \ 4)\) and \(y_2 \in V(P_n^q)\) if \(q \equiv \ 3 \ (mod \ 4)\).
Case 2: whenever \(m \equiv \ 1 \ (mod \ 4)\).
Here also, we apply Lemma 4 to the first three copies of \(P_n\). This gives \(|D|=2\). Now, for \(4 \leq q \leq m-1\), consider the \(q^{th}\) inner copies of \(P_n\) as follows. Let \(D’=x \cup \{y_1,y_2\}\) such that \(x \in V(P_n^{m-1})\) and \(y_1 \in V(P_n^q)\) if \(q \equiv \ 2 \ (mod \ 4)\) and \(y_2 \in V(P_n^q)\) if \(q \equiv \ 3 \ (mod \ 4)\).
Case 3: whenever \(m \equiv \ 2 \ (mod \ 4)\)
Applying Lemma 4 to the first three and last three copies of \(P_n\) we have \(|D|=4\). Next, for \(4 \leq q \leq m-3\), consider the \(q^{th}\) inner copies of \(P_n\) in the following way. Let \(D’=\{y_1,y_2\}\) such that \(y_1 \in V(P_n^q)\) if \(q \equiv \ 2 \ (mod \ 4)\) and \(y_2 \in V(P_n^q)\) if \(q \equiv \ 3 \ (mod \ 4)\).
Furthermore, notice that for each of these cases, every edge in the graph \(G \ \circ \ P_n\) is dominated by a vertex in \((D \cup D’ )\) and \((D \cup D’)\) is minimum. Also, \((G \ \circ \ P_n)\setminus (D \cup D’)\) is connected. This completes the proof.

We now have the following corollary which is immediate from Theorem 5.

Corollary 6. Let \(G\) be a cycle or path of order \(m\) and \(H\) be a cycle of order \(n\) such that \( \ n\geq 5\), then
\(\gamma_{ve}^{oc}(G \ \circ \ C_n)=\left\{\begin{array}{cc} \frac{m+1}{2} ,& \; if \ m \ is \ odd \\ \ \\ \frac{m}{2},& \; if \ m \equiv 0 \ (mod \ 4) \\ \ \\ \frac{m+2}{2} ,& \; otherwise \\ \end{array}\right. \)

Proof. By applying the proof of Theorem 5 to the graph \(G \ \circ \ C_n\), it is not hard to see that the edges of the graph \(G \ \circ \ C_n\) is dominated by \((D \cup D’)\) and \((D \cup D’)\) is minimum. Also, \((G \ \circ \ C_n)\setminus (D \cup D’)\) is not disconnected. Hence the proof.

3.2. Outer-connected vertex edge domination number in \(G \ \circ \ H\)

In this subsection, we provide the outer connected vertex edge domination number of the product \(G \ \circ \ H\) when \(\gamma_{ve}^{oc}(G)=1\).

Theorem 7. Let \(H\) be a simple connected graph and \(n>1\), then
\(\gamma_{ve}^{oc}(K_n \ \circ \ H)=\left\{\begin{array}{cc} 1 ,& \; if \ \gamma_{ve}^{oc}(H)=1 \\ \ \\ 2,& \; otherwise \\ \end{array}\right. \)

Proof. The graph \(K_n \ \circ \ H\) has \(n\) copies of graph \(H\) and the distance between any two pair of vertices of \(K_n \ \circ \ H\) is equal to two. We now split the proof in two cases.
Case 1: whenever \(\gamma_{ve}^{oc}(H)=1\)
Let the vertex \(x \in D\), where \(D\) is the OCVEDS of \(K_n \ \circ \ H\), be a vertex in any of the copy of \(H\) in \(K_n \ \circ \ H\). Clearly, \(D\) dominates the graph \(K_n \ \circ \ H\) and \((K_n \ \circ \ H) \setminus D\) is connected. Hence \(\gamma_{ve}^{oc} (K_n \ \circ \ H)=1\).
Case 2: whenever \(\gamma_{ve}^{oc}(H) \ne 1\)
Let the vertices \(x,y \in D\), where \(D\) is the OCVEDS of \(K_n \ \circ \ H\), be such that \(d_G(x,y)=1\), i.e., \(x\) and \(y\) are not in the same copy of \(K_n\) in \(K_n \ \circ \ H\). Thus \(D\) dominates the graph \(K_n \ \circ \ H\) and \((K_n \ \circ \ H) \setminus D\) is connected. Hence \(\gamma_{ve}^{oc} (K_n \ \circ \ H)=2\). The proof is complete.

Corollary 8. Suppose we have the graph \(G \ \circ \ H\), such that \(\gamma_{ve}^{oc}(G)=1\). If \(\gamma_{ve}^{oc}(H)=\gamma_{ve}^{oc}(G)\), then \(\gamma_{ve}^{oc}(G \ \circ \ H)=1\) and whenever \(\gamma_{ve}^{oc}(H)>1\), \(\gamma_{ve}^{oc}(G \ \circ \ H)=2\).

Proof. The proof of this Corollary can be drawn in the same way as that of Theorem 7.

4. Conclusion

We begin our conclusion with the following remark.

Remark Although the lexicographic product \(G \ \circ \ H\) is commutative, it is seen that the \(\gamma_{ve}^{oc}(G \ \circ \ H)\) may not necessarily be equal to \(\gamma_{ve}^{oc}(H \ \circ \ G)\). For instance, from Corollary 3 and Theorem 7, \(\gamma_{ve}^{oc}(C_m \ \circ \ K_n) \ne \gamma_{ve}^{oc}(K_n \ \circ \ C_m)\), whenever \(m>3\).

So far in this paper, we have provided the outer connected vertex edge domination number of the lexicographic product of two graphs. For some of the products mentioned, the outer connected vertex edge domination number of the graph \(G \ \circ \ H\) depends on either the \(\gamma_{ve}^{oc}(G)\), \(\gamma_{ve}^{oc}(H)\) or both.

Author Contributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Competing Interests

The authors declare that they have no competing interests.