In a graph, a vertex is said to dominate itself and all its neighbors. A subset \(S\subseteq V(G)\) is a double dominating set of a graph \(G\), if every vertex of \(V\) is dominated by at least two vertices of \(S\). The double domination number denoted by \(\gamma_{2\times(G)}\) is the minimum cardinality of a double dominating set. Graph operations are fundamental in graph theory and have various applications across different fields including network analysis, parallel computing and electrical circuit design. This paper studies the problem of finding the double domination number under unary and binary operations of graphs. We investigate the double domination number of graphs under unary operations such as inflation and cubic inflation. Also, we introduced two new unary operations inspired from inflation operation and studied the impact of these operations on double domination number. Further, we explore the double domination number of edge corona and neighborhood corona of two graphs. Additionally, we study the double domination number of various corona operations of two graphs combined with subdivision of a graph and \(R-\)graph.
All graphs we considered are finite, simple and undirected. Let \(G=(V,E)\) be a simple graph with no isolated vertices. The number of vertices, \(|V(G)|\) is called the order of \(G\) and the number of edges \(|E(G)|\) is called the size of \(G\). The open neighborhood of a vertex \(v\in V(G)\) is the set \(N(v)=\{u\in V(G)|uv\in E(G)\}\) and the closed neighborhood of \(v\) is the set \(N[v]=N(v)\cup{v}\). A vertex of degree one is called a pendant vertex and the vertex adjacent to a pendant vertex is called a support vertex. A vertex that is adjacent to all other vertices of a graph is called a universal vertex of the graph. For graph theory terminology and notation, we in general follow [1, 25]. A dominating set of a graph \(G\) is a subset \(D\subseteq V\) such that every vertex of \(V-D\) is adjacent to at least one vertex in \(D\). The domination number, \(\gamma(G)\) is the minimum cardinality of a dominating set of \(G\). For more details we refer the books, Fundamentals of domination in graphs and Topics in domination in graphs[15, 14].
Depending upon various applications, different variations of domination have appeared in the literature. Among them \(k-\)tuple domination is well studied variation of domination. Frank Harary and Teresa Haynes [13, 12] introduced the concept of \(k-\)tuple domination in graphs. The case \(k=2\) corresponds to \(2-\)tuple domination or double domination. A double dominating set of a graph \(G\) is a subset \(D\subseteq V\) such that every vertex in \(V\) is dominated by at least two vertices in \(D\). The double domination number denoted by \(\gamma_{2\times}(G)\) is the minimum cardinality of a double dominating set of \(G\). Equivalently, if \(|N[v]\cap D|\ge 2 \forall v\in V(G)\), then \(D\) is a double dominating set of \(G\).
A detailed survey on double domination in graphs can be found in [15]. The double domination number of trees have been explored in [3, 5]. The double domination problem has been studied under various binary operations such as corona, tensor, join, lexicographic, shadow and rooted products of two graphs in [7, 6, 4, 24]. It has also been studied under various unary operations in [23].
The inflation of a graph is an unary operation which increases the order and the size of the graph but preserves the degree sequence of the graph. The cubic inflation of a graph is an unary operation that converts any connected graph with minimum degree at least two into a cubic graph. The inflation operation of a graph was introduced by Favaron in [9]. Inflation have been studied under various domination parameters in [16, 19, 18]. The cubic inflation operation was introduced in [2].
The corona of two graphs was first introduced by Frucht and Harary [10]. Let \(G_{1}\) and \(G_{2}\) be two graphs on disjoint sets of \(n_{1}\) and \(n_{2}\) vertices, respectively. The corona of \(G_{1}\) and \(G_{2}\), denoted by \(G_{1}\circ G_{2}\), is defined as the graph obtained by taking one copy of \(G_{1}\) and \(n_{1}\) copies of \(G_{2}\), and then joining the \(i^{th}\) vertex of \(G_{1}\) to every vertex in the \(i^{th}\) copy of \(G_{2}\). Hou and Shiu [17] and Gopalapillai [11] introduced the two variants of the corona operation, namely the edge corona and the neighborhood corona respectively. The subdivision operation denoted by \(S(G)\) of a graph \(G\) is the graph obtained by splitting each edge of \(G\) by introducing a new vertex [1]. In [23] we obtained the double domination number of subdivision of some classes of graphs. The two new operations on subdivision graphs, namely, subdivision-vertex corona and subdivision-edge corona were introduced by Lu and Miao [22]. Liu and Lu [21] introduced two new graph operations based on subdivision graphs, namely, the subdivision vertex neighborhood corona and the subdivision edge neighborhood corona. The \(R-\)graph of G, denoted by \(R(G)\) is the graph obtained from \(G\) by adding a vertex \(v\) to every edge \(e\) of \(G\) and joining \(v\) to the end vertices of \(e\) [8]. Observe that R(G) is just the edge corona of \(G\) and \(K_{1}\). In [23] we proved that the double domination number of \(R-\)graph of any graph \(G\) is the order of \(G\). Lan and nZhou[20] defined four new graph operations based on \(R-\)graphs, namely the \(R-\)vertex corona, \(R-\)edge corona, \(R-\)vertex neighborhood corona and \(R-\)edge neighborhood corona.
Although the double domination number of various unary operations and vertex corona has been explored, the double domination number of inflation, cubic inflation, edge corona, neighborhood corona and various corona operations combined with subdivision and \(R-\)graph has not been examined so far. This inspired us to study the double domination problem under inflation and various corona operations.
The rest of the paper is organized as follows. In Section 2, we obtain the double domination number of inflation, cubic inflation and two new unary operations of graphs. In Section 3, we determine the double domination number of edge corona, neighborhood corona and various corona operations of two graphs combined with subdivision of a graph and \(R-\)graph respectively.
Observation 1.1. [24] Every double dominating set of a graph must contain all its leaves and support vertices.
Theorem 1.2. [24] For a connected graph \(G\), \(\gamma_{2\times}(G)=2\) if and only if \(G\) has at least two universal vertices.
Theorem 1.3. [24] For a connected graph \(G\), \(\gamma_{2\times}(G)=|V(G)|\) if and only if every vertex of the \(G\) is either a leaf or a support vertex.
Theorem 1.4. [24] If \(G\) is a graph without isolated vertices then \(\gamma_{2\times}(G) \ge \frac{2n}{\Delta(G)+1}\).
Theorem 1.5. [24] Let \(G\) be a cycle graph of order \(n\). Then \(\gamma_{2\times}(C_{n})=\left\lceil\frac{2n}{3}\right\rceil\).
Theorem 1.6. [24] Let \(G\) be a path graph of order \(n\). Then \(\gamma_{2\times}(P_{n})=\left\lceil\frac{2(n+1)}{3}\right\rceil\).
Definition 2.1. The inflation of \(G\) or inflated graph \(G_{I}\) is obtained as follows: every vertex \(x\in V(G)\) of degree \(d(x)\) is replaced by a clique \(X=K_{d(x)}\) and each edge \(xy\) is an edge between two vertices \(x\) and \(y\) of the corresponding cliques \(X\) and \(Y\) of \(G_{I}\) in such a way that the edges of \(G_{I}\) which come from the edges of \(G\) form a matching.
As an obvious consequence of the definition of inflation, \(n(G_{I})=\sum\limits_{x_{i}\in V(G)}d(x_{i})=2m(G)\) and \(\Delta(G_{I})=\Delta(G)\) and \(\delta(G_{I})=\delta(G)\). For the notations of inflated graphs we follow [9]. A graph \(G\) and its inflated graph \(G_{I}\) are shown in Figure 1.
Theorem 2.2. Let \(G\) be a graph of order \(n\) with no isolated vertices. Then \(n\le \gamma_{2\times}(G_{I})\le 2n\).
Proof. Let \(\{v_{i};1\le i\le
n\}\) be the vertices of \(G\).
Let \(K_{d(v_{i})}; v_{i}\in V(G)\) be
the cliques of \(G_{I}\). Let \(S\) be the minimum double dominating set of
\(G_{I}\). Then \(S\) must contain at least one vertex from
each of the cliques in \(G_{I}\),
because a vertex \(v\) in \(G_{I}\) has only one neighbor outside \(K_{d(v)}\). Since, there are \(n\) cliques in \(G_{I}\), to double dominate every vertex of
\(G_{I}\) we need at least \(n\) vertices. This implies, \(|S|\ge n\).
Every clique \(K_{d(v_{i})}\) has at
least two universal vertices and thus by Theorem 1.2, we have, \(\gamma_{2\times}(K_{d_{v_{i}}})=2\) for
each \(i;1\le i\le n\). Hence, \(\gamma_{2\times}(G_{I})\le
\sum\limits_{i=1}^{n}\gamma_{2\times}(K_{d_{v_{i}}})=2n\). ◻
Theorem 2.3. Let \(G\) be a graph without isolated vertex. Then \(\gamma_{2\times}(G_{I})\ge 2l(G)\), where \(l(G)\) is the number of leaves in \(G\) with equality if and only if every vertex of \(G\) is either a leaf or a support vertex.
Proof. Let \(S\) be the minimum double dominating set of \(G_{I}\). Let \(x_{i}\) be a leaf adjacent to \(y_{i}\). Since every vertex \(v\in V(G)\) is replaced by a clique of size \(deg(v)\), a leaf in \(G\) remains as a leaf in \(G_{I}\). Also each leaf in \(G_{I}\) is adjacent to a unique vertex in \(G_{I}\). Therefore, to double dominate every leaf of \(G_{I}\), we need every leaf and its support vertex to be in the minimum double dominating set \(S\) of \(G_{I}\). Hence, \(|S|\ge 2l(G)\).
Suppose \(|S|=2l(G)\) be a minimum double dominating set of \(G_{I}\). Let \(u\) be the vertex which is neither a leaf nor a support vertex in \(G\). Then by definition of \(G_{I}\) \(u\) cannot be adjacent to any of the support vertex in \(G_{I}\). Thus \(u\) is not dominated even once, contradicting the fact that \(S\) is the minimum double dominating set of \(G_{I}\).
Conversely, suppose every vertex in the graph \(G\) is either a leaf or a support vertex. Then by observation 1, and by the fact that every leaf of \(G_{I}\) is adjacent to a unique support vertex, \(S\) contains every leaf and support vertex of \(G_{I}\) to double dominate them. ◻
Theorem 2.4. Let \(G\cong C_{n}\) be the cycle graph of order \(n\). Then \(\gamma_{2\times}(G_{I})=\left\lceil\frac{4n}{3}\right\rceil\).
Proof. The inflation of cycle of order \(n\) is again a cycle of order \(2n\). Therefore by Theorem 1.5, \(\gamma_{2\times}(G_{I})=\left\lceil\frac{4n}{3}\right\rceil\). ◻
Theorem 2.5. Let \(G\cong P_{n}\) be the path graph of order \(n\). Then \(\gamma_{2\times}(G_{I})=\left\lceil\frac{4(n-2)}{3}\right\rceil\).
Proof. The inflation of path of order \(n\) is again a path of order \(2(n-1)\). Therefore by Theorem 1.6, \(\gamma_{2\times}(G_{I})=\left\lceil\frac{4(n-2)}{3}\right\rceil\). ◻
Theorem 2.6. Let \(G\cong W_{n}\) be the wheel graph of order \(n\). Then \(\gamma_{2\times}(G_{I})=\left\lceil\frac{2(n-1)}{3}\right\rceil+\left\lceil\frac{n-1}{2}\right\rceil\).
Proof. Let \(\{v_{i};1\le i\le n\}\) be the vertices of \(G\). Let \(v_{n}\) be the universal vertex of \(G\). Then each \(v_{i};1\le i\le n-1\) are replaced by a clique of size 3 and \(v_{n}\) is replaced by a clique of size \(deg(v_{n})\) in \(G_{I}\). Let \(\{v_{i,1},v_{i,2},v_{i,3};1\le i\le n-1\}\) be the vertices of the cliques, \(K_{v_{i}};1\le i\le n-1\) corresponding to the vertices \(v_{i};1\le i\le n-1\). Let \(\{v_{i,3};1\le i\le n-1\}\) be the vertices adjacent to the vertices in the clique, \(K_{v_{n}}\) corresponding to \(v_{n}\) in \(G_{I}\). Then the vertices \(\{v_{i,1},v_{i,2};1\le i\le n-1\}\) form a cycle of length \(2(n-1)\). Let \(S\) be the double dominating set of \(G_{I}\). We pick the minimum double dominating set \(\{v_{i,j};1\le i\le n-1;j=1,2;i+j\not\equiv0\mod3\}\) of the cycle to be in \(S\). Then the vertices in this cycle are dominated at least twice. Observe that, \(S\) contains two vertices from cliques \(K_{v_{i}};1\le i\le n-1;i\equiv1\mod3\) and exactly one vertex from the cliques \(K_{v_{i}};1\le i\le n-1;i\not\equiv1\mod3\). Hence, \(S\) dominates vertices in \(K_{v_{i}};1\le i\le n-1;i\equiv1\mod3\) at least twice. Now there are \(\left\lceil\frac{n-1}{2}\right\rceil\) vertices, \(\{v_{i,3}\}\) of the cliques \(K_{v_{i}};1\le i\le n-1;i\not\equiv1\mod3\) that are adjacent to the vertices in the clique \(K_{v_{n}}\) that is dominated only once by \(S\). Hence, we include the vertices \(\{v_{n,i};1\le i\le n-1;i\not\equiv1\mod3\}\) from \(K_{v_{n}}\) that are the neighbors of the vertices \(\{v_{i,3}\}\) of the cliques \(K_{v_{i}};1\le i\le n-1;i\not\equiv1\mod3\) in \(S\). This set \(S=\{v_{i,j};1\le i\le n-1;j\not\equiv0\mod3\}\cup\{v_{n,i};1\le i\le n-1;i\not\equiv1\mod3\}\) dominates every vertex of \(G_{I}\) at least twice and \(|S|=\left\lceil\frac{4(n-1)}{3}\right\rceil+\left\lceil\frac{n-1}{2}\right\rceil\). Now, we need to prove \(S\) is the minimum double dominating set of \(G_{I}\). Since the double domination number is the minimum among cardinality of all the double dominating sets of \(G_{I}\) we have \(\gamma_{2\times}(G_{I})\le |S|= \left\lceil\frac{4(n-1)}{3}\right\rceil+\left\lceil\frac{n-1}{2}\right\rceil\).
To dominate every vertex of \(G_{I}\) at least twice we need to include two vertices from each clique that is \(2n\) vertices which is greater than \(|S|\). Otherwise we need to include the minimum dominating set \(\{v_{i,j};1\le i\le n-1;j=1,2;j\equiv i\mod3\}\) of the cycle of length \(2(n-1)\). Then Let \(S'=S-\{u\}\) for any \(u\) in \(S\). This set \(S'\) dominates every vertex of \(G_{I}\) at least twice except the neighbors of \(u\). This implies, \(\gamma_{2\times}(G_{I})\ge \left\lceil\frac{2(n-1)}{3}\right\rceil+\left\lceil\frac{n-1}{2}\right\rceil=|S|\). This proves \(S\) is the minimum double dominating set of \(G_{I}\) and \(\gamma_{2\times}(G_{I})=\left\lceil\frac{2(n-1)}{3}\right\rceil+\left\lceil\frac{n-1}{2}\right\rceil\). ◻
Theorem 2.7. Let \(G\cong K_{n}\) be the complete graph of order \(n\). Then \(\gamma_{2\times}(G_{I})=2(n-1)\).
Proof. Let \(\{v_{i};1\le i\le n\}\) be the vertices of \(G\) and \(K_{v_{i}}\) be the cliques corresponding to the vertex \(v_{i}\). Let \(\{v_{j,k};1\le j\le n;1\le i,k\le d(v_{i})\}\) be the vertices of the cliques \(K_{v_{i}};1\le i\le n\). Let \(S=\{v_{1,1},v_{2,1},v_{j,k};3\le j\le n; 1\le k\le d(v_{i})\}\) where \(v_{j,k}\in \{N(v_{1,1})\cup N(v_{2,1})\}-\{K_{v_{1}}\cup K_{v_{2}}\}\) and \((v_{1,1},v_{2,1})\in E(G_{I})\). This set \(S\) dominates every vertex of \(G_{I}\) at least twice. Therefore, \(S\) is the double dominating set of \(G_{I}\) and \(|S|=2(n-1)\). Now we need to prove \(S\) is minimum. From the definition of double domination number it is obvious that \(\gamma_{2\times}(G_{I})\le |S|=2(n-1)\). Observe that every vertex in a clique has a unique neighbor from another clique. This implies, no two vertices of a clique \(K_{v_{i}}\) have a common neighbor outside \(K_{v_{i}}\). Therefore, to dominate all the vertices of a clique at least twice, we need to include two vertices from each clique or one vertex from the clique and its neighbor from another clique. In both the cases, \(\gamma_{2\times}(G_{I})=2n\ge |S|=2(n-1)\). Thus, \(S\) is a minimum double dominating set of \(G_{I}\). Hence \(\gamma_{2\times}(G_{I})=2(n-1)\). ◻
Theorem 2.8. Let \(G\cong K_{m,n}\) be the complete bipartite graph of order \(m+n\). Then \(\gamma_{2\times}(G_{I})=2(m+n-1)\).
Proof. The proof of this theorem is similar to the proof of the previous theorem. Let \(\{v_{i},v_{j};1\le i\le m;1\le j\le n\}\) be the vertices of \(G\) and \(K_{v_{i}}, K_{v_{j}}\) be the cliques corresponding to the vertex \(v_{i}\) and \(v_{j}\) respectively. Let \(\{v_{k,l};1\le k\le m;1\le l\le d(v_{i})\}\) be the vertices of the cliques \(K_{v_{i}}\) and \(\{v_{p,q};m+1\le p\le n;1\le q\le d(v_{j})\}\) be the vertices of the cliques \(K_{v_{j}}\). Let \(S=\{v_{1,1},v_{2,1},v_{k,l},v_{p,q};3\le k\le m; 1\le l\le 2; m+1\le p\le n; 1\le q\le d(v_{i})\}\) where \(v_{p,q}\in \{N(v_{1,1})\cup N(v_{2,1})\}-\{K_{v_{1}}\cup K_{v_{2}}\}\). This set \(S\) dominates every vertex of \(G_{I}\) at least twice. Therefore, \(S\) is the double dominating set of \(G_{I}\) and \(|S|=2(m+n-1)\). Now we need to prove \(S\) is minimum. From the definition of double domination number it is obvious that \(\gamma_{2\times}(G_{I})\le |S|=2(m+n-1)\). Observe that every vertex in a clique has a unique neighbor from another clique. This implies, no two vertices of a clique \(K_{v_{i}}\) have a common neighbor outside \(K_{v_{i}}\). Therefore, to dominate all the vertices of a clique at least twice, we need to include two vertices from each clique or one vertex from the clique and its neighbor from another clique. In both the cases, \(\gamma_{2\times}(G_{I})=2(m+n)\ge |S|=2(m+n-1)\). Thus, \(S\) is a minimum double dominating set of \(G_{I}\). Hence, \(\gamma_{2\times}(G_{I})=2(m+n-1)\). ◻
Theorem 2.9. Let \(G\cong K_{1,n}\) and \(G'\cong S_{r,t}\) be a star graph and a double star graph of order \(n+1\) and \(r+t\) respectively. Then \(\gamma_{2\times}(G_{I})= 2l(G)\) and \(\gamma_{2\times}(G'_{I}) = 2l(G' )\) where \(l(G)\) is the number of leaves in \(G\).
Proof. The proof follows from the Theorem 2.3. ◻
Observe that the inflation operation increases the double domination number as the number of vertices and edges increases. Also the gap between \(\gamma_{2\times}(G)\) and \(\gamma_{2\times}(G_{I})\) can be arbitrarily large. For example, \(\gamma_{2\times}(K_{n})=2\) but \(\gamma_{2\times}(K_{nI})=2(n-1)\).
Definition 2.10. Let \(G\) be a connected graph without isolated vertices. The cubic inflation of graph \(G\) denoted by \(CI(G)\) is obtained as follows: First we replace every vertex \(v\) with a cycle \(Q_{v}\) of length twice the degree of \(v\) and then replace every edge \(uv\) of \(G\) by two edges joining \(Q_{u}\) and \(Q_{v}\).
A graph \(G\) and its cubic inflation \(CI(G)\) are shown in Figure 2. From the definition we have \(n(CI(G))=\sum\limits_{v\in V(G)}2deg(v)=4m(G)\) [2].
Theorem 2.11. Let \(G\) be a connected graph of order n and size \(m\), with \(\delta(G)\ge 2\). Then \(\gamma_{2\times}(CI(G))=2m\).
Proof. Let \(\{v_{i};1\le i\le n\}\) be the vertices of \(CI(G)\). Let \(C_{v_{i}}\) be the cycles of order \(2deg(v_{i})\) in \(CI(G)\) corresponding to the vertices \(v_{i}\). Let \(\{v_{i,j};1\le i\le n; 1\le j\le 2deg(v_{i})\}\) be the vertices of the cycles \(C_{v_{i}}\). Let \(S\) be the double dominating set of \(CI(G)\). We pick the vertices \(\{v_{i,j};1\le i\le n; j=even\}\) from each cycle \(C_{v_{i}}\) to \(S\) in such a way that \((v_{i,j},v_{k,j})\in E(CI(G));1\le i,k\le n;i\ne k\). That is we pick \(deg(v_{i})\) vertices from each cycle and there are \(n\) cycles. Therefore, \(|S|=\sum\limits_{i=1}^{n}deg(v_{i})=2m\). From Theorem 1.4, we have \(\gamma_{2\times}(CI(G))\ge \frac{2n(CI(G))}{\Delta(CI(G))+1}=\frac{8m}{4}=2m\). This implies, \(S\) is the minimum double dominating set of \(CI(G)\) and hence \(\gamma_{2\times}(CI(G))=2m\). ◻
Definition 2.12. Let \(G\) be a connected graph of order \(n\). Let \(G_{\alpha}\) be the graph obtained after applying \(\alpha\) – operation on \(G\). The operation is defined as follows: every vertex \(v\in V(G)\) is replaced by the independent set, \(I_{v}\) of cardinality \(deg(v)\) and every vertex of \(I_{v}\) is adjacent to every vertex of \(I_{u}\) if \(uv\in E(G)\). \(G_{\alpha}\) has \(\sum\limits_{i=1}^{n}deg(v_{i})\) vertices.
A graph \(G\) and the graph \(G_{\alpha}\) obtained after applying \(\alpha\) – operation on \(G\) are shown in Figure 3.
Theorem 2.13. Let \(G\) be a connected graph of order \(n\) and with a universal vertex or two vertices \(u\) and \(v\) such that \(N[u]\cup N[v]=V(G)\). Then \(\gamma_{2\times}(G_{\alpha})=4\).
Proof. Let \(\{v_{i};1\le i\le n\}\) be the vertices of \(G\). Then each vertex \(v_{i}\) is replaced by an independent set \(I_{v_{i}}\) of size \(deg(v_{i})\) in \(G_{\alpha}\). Let \(v_{n}\) be the universal vertex of \(G\) and \(I_{v_{n}}\) be the independent set corresponding to the vertex \(v_{n}\). Since \(v_{n}\) is a universal vertex, every vertex in \(I_{v_{n}}\) is connected to every vertex in \(I_{v_{i}};1\le i\le n-1\). Therefore, any two vertices from the independent set \(I_{v_{n}}\) will dominate every vertex of \(G_{\alpha}\) at least twice except the vertices in \(I_{v_{n}}\). Since vertices in \(I_{v_{n}}\) share no edges between them, in order to double dominate the vertices in \(I_{v_{n}}\) choose any two vertices from any of the independent sets \(I_{v_{i}};1\le i\le n-1\). This implies, \(\gamma_{2\times}(G_{\alpha})=4\).
Similarly, let \(u\) and \(v\) be two vertices of \(G\) such that \(N[u]\cup N[v]=V(G)\) and \(I_{u}\) and \(I_{v}\) be the independent sets corresponding to the vertices \(u\) and \(v\) respectively. In this case, any two vertices from each of the independent sets \(I_{u}\) and \(I_{v}\) will dominate every vertex of \(G_{\alpha}\) at least twice. Hence, \(\gamma_{2\times}(G_{\alpha})=4\). ◻
Theorem 2.14. Let \(G\cong C_{n}\) be the cycle graph of order \(n\). Then \(\gamma_{2\times}(G_{\alpha})=n\).
Proof. Let \(\{v_{i};1\le i\le n\}\) be the vertices of \(G\). Each \(v_{i}\) is replaced by an independent set \(I_{v_{i}}\) of size \(2\) in \(G_{\alpha}\). Let \(\{v_{i,1},v_{i,2};1\le i\le n\}\) be the vertices of \(G_{\alpha}\). Let the set \(S=\{v_{i,1};1\le i\le n\}\). This set \(S\) dominates every vertex of \(G_{\alpha}\) at least twice because these vertices form a cycle of length \(n\) and the vertices \(\{v_{i,2};1\le i\le n\}\) are adjacent to exactly two vertices of \(S\). Therefore \(S\) is a double dominating set of \(G_{\alpha}\). Now we need to prove \(S\) is minimum. From the definition of double domination number it is obvious that \(\gamma_{2\times}(G_{\alpha})\le |S|=n\). In \(G_{\alpha}\), each vertex is replaced by an independent set of size 2 and the resulting graph is a 4-regular graph. The vertices in each independent set have four neighbors in common. But these four neighbors share no edges among them. Therefore, to dominate every vertex at least twice we need to include the vertex and one of its neighbors or two of the neighbors of each vertex and one more vertex common to these two neighbors. In both the cases, we need at least \(n\) vertices to dominate every vertex of \(G_{\alpha}\) at least twice. This implies, \(S\) is the minimum double dominating set of \(G_{\alpha}\) and hence \(\gamma_{2\times}(G_{\alpha})=n\). ◻
Theorem 2.15. Let \(G\cong P_{n}\) be the path graph of order \(n\). Then , \[\gamma_{2\times}(G_{\alpha})= \begin{cases} n-1, \quad \text{$n\equiv 1\mod3$},\\ n, \quad \text{otherwise}. \end{cases}\]
Proof. Let \(\{v_{i};1\le i\le n\}\) be the vertices of \(G\). Each \(v_{i};2\le i\le n-1\) is replaced by an independent set \(I_{v_{i}}\) of size \(2\) and the vertices \(v_{1},v_{n}\) are replaced by the independent sets \(I_{v_{1}}\), \(I_{v_{n}}\) of size 1 in \(G_{\alpha}\). Let \(\{v_{1,1},v_{n,1},v_{i,1},v_{i,2};2\le i\le n-1\}\) be the vertices of \(G_{\alpha}\).
Case 1. When \(n\not\equiv 1\mod3\).
Let us consider the set \(S=\{v_{2,1},v_{2,2},v_{n-1,1},v_{n-1,2},v_{i,1},v_{i+1,2};2\le i,\le n-3;i\equiv2\mod3\}\). This set \(S\) dominates every vertex of \(G_{\alpha}\) at least twice. Therefore, \(S\) is a double dominating set of \(G_{\alpha}\). Now we need to prove \(S\) is minimum. From the definition of double domination number it is obvious that \(\gamma_{2\times}(G_{\alpha})\le |S|=n\). In \(G_{\alpha}\), each vertex is replaced by an independent set of size 2 except for the vertices \(v_{1}\) and \(v_{n}\). The vertices in each independent set \(I_{v_{i}};3\le i\le n-2\) have four neighbors in common. But these four neighbors share no edges among them. Therefore, to dominate every vertex at least twice we need to include the vertex and one of its neighbors or two of the neighbors of each vertex and one more vertex common to these two neighbors. In both the cases, we need at least \(n\) vertices to dominate every vertex of \(G_{\alpha}\) at least twice. This implies, \(S\) is the minimum double dominating set of \(G_{\alpha}\). Hence, \(\gamma_{2\times}(G_{\alpha})=|S|=n\).
Case 2. When \(n\equiv1\mod3\).
In this case consider the set \(S=\{v_{2,1},v_{2,2},v_{n-1,1},v_{n-1,2},v_{i,1},v_{i+1,2};2\le i,j\le n-3;i\equiv2\mod3\}-\{v_{n-3,2}\}\). This set \(S\) dominates every vertex of \(G_{\alpha}\) at least twice. Therefore, \(S\) is a double dominating set of \(G_{\alpha}\). Now we need to prove \(S\) is minimum. The same set as in the previous case without the vertex \(v_{n-3,2}\) acts as the minimum double dominating set for this case. This implies, \(S\) is the minimum double dominating set of \(G_{\alpha}\) with \(|S|=n-1\). Hence, \(\gamma_{2\times}(G_{\alpha})=|S|=n-1\). ◻
Definition 2.16. Let \(G\) be a connected graph of order \(n\). Let \(G_{\beta}\) be the graph obtained after applying \(\beta\) – operation on \(G\). The operation is defined as follows: every vertex \(v\in V(G)\) is replaced by the path, \(P_{v}\) of order \(deg(v)\) and every vertex of \(P_{v}\) is adjacent to every vertex of \(P_{u}\) if \(uv\in E(G)\). \(G_{\beta}\) has \(\sum\limits_{i=1}^{n}deg(v_{i})\) vertices.
In Figure 4, we present a graph \(G\) and the graph \(G_{\beta}\) obtained after applying \(\beta\) – operation on \(G\).
Theorem 2.17. Let \(G\) be a connected graph of order \(n\) and with a universal vertex or two vertices \(u\) and \(v\) such that \(N[u]\cup N[v]=V(G)\). Then for \(n\ge 6\), \(\gamma_{2\times}(G_{\beta})=4\).
Proof. The proof is similar to the proof of Theorem 2.13. Let \(\{v_{i};1\le i\le n\}\) be the vertices of \(G\). Then each vertex \(v_{i}\) is replaced by a path \(P_{v_{i}}\) of order \(deg(v_{i})\) in \(G_{\beta}\). Let \(v_{n}\) be the universal vertex of \(G\) and \(P_{v_{n}}\) be the path corresponding to the vertex \(v_{n}\). Since \(v_{n}\) is a universal vertex, every vertex in \(P_{v_{n}}\) is connected to every vertex in \(P_{v_{i}};1\le i\le n-1\). Therefore, any two vertices from the path \(P_{v_{n}}\) will dominate every vertex of \(G_{\beta}\) at least twice except the vertices in \(P_{v_{n}}\). Since vertices in \(P_{v_{n}}\) is a path of order \(deg(v_{i})\), any two vertices of \(P_{v_{n}}\) is not sufficient to double dominate the vertices in \(P_{v_{n}}\). Therefore, choose any two vertices from any of the paths \(P_{v_{i}};1\le i\le n-1\). This implies, \(\gamma_{2\times}(G_{\beta})=4\).
Similarly, let \(u\) and \(v\) be two vertices of \(G\) such that \(N[u]\cup N[v]=V(G)\) and \(P_{u}\) and \(P_{v}\) be the paths corresponding to the vertices \(u\) and \(v\) respectively. In this case, any two vertices from each of the paths \(P_{u}\) and \(P_{v}\) will dominate every vertex of \(G_{\beta}\) at least twice. Hence, \(\gamma_{2\times}(G_{\beta})=4\). ◻
Corollary 2.18. Let \(G\) be a connected graph of order \(n\) and with a universal vertex or two vertices \(u\) and \(v\) such that \(N[u]\cup N[v]=V(G)\). Then for \(n<6\), \(\gamma_{2\times}(G_{\beta})=3\).
Proof. Since \(n<6\), the degree of the universal vertex \(u\) will be less than or equal to \(4\). Therefore, the order of the path \(P_{u}\) replaced instead of \(u\) will be less than or equal to \(4\). Therefore, any two vertices from \(P_{u}\) will dominate every vertex of \(G_{\beta}\) at least twice but the vertices in the path \(P_{u}\) corresponding to \(u\) is dominated only once by those two vertices. To dominate these vertices at least twice its enough to pick any vertex of \(G_{\beta}\) other than the vertices in \(P_{u}\). Therefore, for \(n<6\), \(\gamma_{2\times}(G_{\beta})=4\).
Similarly, let \(u\) and \(v\) be two vertices such that \(N[u]\cup N[v]=V(G)\). Then for \(n<6\), \(\gamma_{2\times}(G_{\beta})=3\). ◻
Theorem 2.19. Let \(G\cong C_{n}\) be the cycle graph of order \(n\). Then \(\gamma_{2\times}(G_{\beta})=\gamma_{2\times}(G)\).
Proof. Let \(\{v_{i};1\le i\le n\}\) be the vertices of \(G\). Each \(v_{i}\) is replaced by a path \(P_{v_{i}}\) of order \(2\) in \(G_{\beta}\). Let \(\{v_{i,1},v_{i,2};1\le i\le n\}\) be the vertices of \(G_{\beta}\). Note that the set \(S_{G}=\{v_{i};1\le i\le n;i\not\equiv0\mod3\}\) is the minimum double dominating set of \(G\) and \(\gamma_{2\times}(G)=\left\lceil\frac{2n}{3}\right\rceil\). Now consider the set \(S_{G_{\beta}}=\{v_{i,1};1\le i\le n;i\not\equiv0\mod3\}\). This set dominates every vertex of \(G_{\beta}\) at least twice because, these vertices form a cycle of length \(n\) and the vertices \(\{v_{i,2};1\le i\le n\}\) are adjacent to exactly two vertices of \(S_{G_{\beta}}\) and therefore \(S_{G_{\beta}}\) is a double dominating set of \(G_{\beta}\) and \(|S|=\left\lceil\frac{2n}{3}\right\rceil=\gamma_{2\times(G)}\). Now we need to prove \(S_{G_{\beta}}\) is minimum. From Theorem 1.4, we have \(\gamma_{2\times}({G_{\beta}})\ge \frac{2(n(G_{\beta}))}{\Delta(G_{\beta})+1}=\frac{4n}{6}=\frac{2n}{3}\). This implies, \(S_{G_{\beta}}\) is the minimum double dominating set of \(G_{\beta}\) and hence \(\gamma_{2\times}(G_{\beta})=\gamma_{2\times}(G)\). ◻
Theorem 2.20. Let \(G\cong P_{n}\) be the path graph of order \(n\). Then, \[\gamma_{2\times}(G_{\beta})= \begin{cases} \left\lceil\frac{2(n+1)}{3}\right\rceil-1, \quad \text{$n\equiv 0\mod3$},\\ \left\lceil\frac{2(n+1)}{3}\right\rceil, \quad \text{otherwise}. \end{cases}\]
Proof. Let \(\{v_{i};1\le i\le n\}\) be the vertices of \(G\). Each \(v_{i};2\le i\le n-1\) is replaced by a path \(P_{v_{i}}\) of order \(2\) and the vertices \(v_{1},v_{n}\) are replaced by the path \(P_{v_{1}}\), \(P_{v_{n}}\) of size 1 in \(G_{\beta}\). Let \(\{v_{1,1},v_{n,1},v_{i,1},v_{i,2};2\le i\le n-1\}\) be the vertices of \(G_{\beta}\).
Case 1. When \(n\not\equiv 0\mod3\).
Let us consider the set \(S=\{v_{2,1},v_{2,2},v_{n-1,1},v_{n-1,2},v_{i,1},v_{i,2};3\le i\le n-3;i\equiv2\mod3\}\). This set \(S\) dominates every vertex of \(G_{\beta}\) at least twice. Therefore, \(S\) is a double dominating set of \(G_{\beta}\). Now to prove \(S\) is minimum. From the definition of double domination number it is obvious that \(\gamma_{2\times}(G_{\beta})\le |S|=\left\lceil\frac{2(n+1)}{3}\right\rceil\). In \(G_{\beta}\), each vertex is replaced by a path of order 2 except for the vertices \(v_{1}\) and \(v_{n}\). The vertices in each path \(P_{v_{i}};3\le i\le n-2\) have five neighbors in common. But these five neighbors share no edges among them. Therefore, to dominate every vertex at least twice we need to include the vertex and one of its neighbors or two of the neighbors of each vertex and one more vertex common to these two neighbors. In both the cases, we need at least \(n\) vertices to dominate every vertex of \(G_{\beta}\) at least twice. This implies, \(S\) is the minimum double dominating set of \(G_{\beta}\). Hence, \(\gamma_{2\times}(G_{\beta})=|S|=\left\lceil\frac{2(n+1)}{3}\right\rceil\).
Case 2. When \(n\equiv0\mod3\).
In this case, the same set \(S=\{v_{2,1},v_{2,2},v_{n-1,1},v_{n-1,2},v_{i,1},v_{i,2};3\le i,j\le n-3;i\equiv2\mod3\}\) dominates every vertex of \(G_{\beta}\) at least twice but \(|S|=\left\lceil\frac{2(n+1)}{3}\right\rceil-1\). Therefore, \(S\) is a double dominating set of \(G_{\beta}\) which is minimum. Hence, \(\gamma_{2\times}(G_{\beta})=|S|=\left\lceil\frac{2(n+1)}{3}\right\rceil-1.\) ◻
Definition 3.1. [17] Let \(G_{1}\) and \(G_{2}\) be two graphs on disjoint sets \(n_{1}\) and \(n_{2}\) vertices, \(m_{1}\) and \(m_{2}\) edges respectively. The edge corona \(G_{1}\diamond G_{2}\) is defined as the graph obtained by taking one copy of \(G_{1}\) and \(m_{1}\) copies of \(G_{2}\) and joining two end vertices of \(i^{th}\) edge of \(G_{1}\) to every vertex in the \(i^{th}\) copy of \(G_{2}\). \(G_{1}\diamond G_{2}\) has \(n_{1}+m_{1}n_{2}\) vertices and \(m_{1}+2m_{1}n_{2}+m_{1}m_{2}\) edges. For example consider the edge corona graph of a cycle of order \(3\) and a path of order \(2\), \(C_{3}\diamond P_{2}\), see Figure 5.
Theorem 3.2. Let \(G_{1}\) and \(G_{2}\) be two graphs of order \(n_{1}\) and \(n_{2}\) and size \(m_{1}\) and \(m_{2}\) respectively. Then \(\gamma_{2\times}(G_{1}\diamond G_{2})=n_{1}\).
Proof. Let \(G_{1}\) and \(G_{2}\) be two graphs of order \(n_{1}\) and \(n_{2}\) respectively. Then \(G_{1}\diamond G_{2}\) has \(n_{1}+m_{1}n_{2}\) vertices. Let \(|E(G_{1})|=m_{1}\) and \(|E(G_{2})|=m_{2}\). Let \(\{v_{1},v_{2},\cdots,v_{n_{1}}\}\) be the vertices of \(G_{1}\) and \(\{e_{1},e_{2},\cdots,e_{m_{1}}\}\) be the edges of \(G_{1}\). Consider the set \(S=\{v_{1},v_{2},\cdots,v_{n_{1}}\}\). This set dominates every vertex of \(G_{1}\diamond G_{2}\) at least twice. Therefore, \(S\) is a double dominating set of \(G_{1}\diamond G_{2}\) and \(|S|=n_{1}\). Now we need to prove \(S\) is minimum. Since \(S\) is a double dominating set of \(G_{1}\diamond G_{2}\) and \(|S|=n_{1}\) and the minimum double dominating set of a graph is the minimum cardinality among all the double dominating sets of a graph, we have, \(\gamma_{2\times}(G_{1}\diamond G_{2})\le n_{1}=|S|\). In \(G_{1}\diamond G_{2}\), to double dominate every vertex of each copy of \(G_{2}\) we either need to include the minimum double dominating set of each copy of \(G_{2}\) or the minimum dominating set of each copy of \(G_{2}\) and one of the endpoints of each edge of \(G_{1}\). In both the cases, \(|S|\ge n_{1}\). Observe that every vertex of each copy of \(G_{2}\) is adjacent to exactly two vertices of \(G_{1}\) in \(G_{1}\diamond G_{2}\). Therefore, we need all the vertices of \(G_{1}\) to double dominate every vertex of each copy of \(G_{2}\). This proves \(S=\{v_{1},v_{2},\cdots,v_{n_{1}}\}\) is minimum. Hence, \(\gamma_{2\times}(G_{1}\diamond G_{2})=|S| = n_{1}\). ◻
Definition 3.3. [11] Let \(G_{1}\) and \(G_{2}\) be two graphs on \(n_{1}\) and \(n_{2}\) vertices, \(m_{1}\) and \(m_{2}\) edges respectively. Then the neighborhood corona \(G_{1}\star G_{2}\) is the graph obtained by taking \(n_{1}\) copies of \(G_{2}\) and for each \(i\), making all vertices in the \(i^{th}\) copy of \(G_{2}\) adjacent with neighbors of \(v_{i}\), \(i=1,2,…,n_{1}\).
\(G_{1}\star G_{2}\) has \(n_{1}+n_{1}n_{2}\) vertices and \(m_{1}(2n_{2}+1)+n_{1}m_{2}\) edges. For example, consider the neighborhood corona of cycle of order 3 and path of order 3, \(C_{3}\star P_{3}\), see Figure 6.
Theorem 3.4. Let \(G_{1}\) be a graph of order \(n_{1}\) whose vertices are either a pendant or a support vertex and let \(G_{2}\) be a graph of order \(n_{2}\). Then \(\gamma_{2\times}(G_{1}\star G_{2})=n_{1}+l.\gamma(G_{2})\) where \(l\) is the number of pendant vertices in \(G_{1}\).
Proof. Let \(G_{1}\) be a graph whose vertices are either pendant or a support vertex. Observe that the pendant vertices have only one neighbor and so every vertex in the copies of \(G_{2}\) with respect to the pendant vertices of \(G_{1}\) are adjacent to exactly one vertex of \(G_{1}\) in \(G_{1}\star G_{2}\). But the vertices in the copies of \(G_{2}\) with respect to the support vertices of \(G_{1}\) are adjacent to at least two vertices of \(G_{1}\). Therefore, the set \(S=\{v_{i};1\le i\le n_{1}\}\) dominates every vertex of \(G_{1}\star G_{2}\) at least twice but the vertices in the copies of \(G_{2}\) with respect to the pendant vertices are dominated only once by \(S\). Therefore, we include the minimum dominating set of each copy of \(G_{2}\) with respect to the pendant vertices to \(S\). This \(S\) dominates every vertex of \(G_{1}\star G_{2}\) at least twice. Therefore, \(S\) is the double dominating set of \(G_{1}\star G_{2}\) which is minimum. Hence, \(\gamma_{2\times}(G_{1}\star G_{2})=n_{1}+l.\gamma(G_{2})\). ◻
Theorem 3.5. Let \(G_{1}\) be a graph with at least two universal vertices and of order \(n_{1}\) and \(G_{2}\) be a graph of order \(n_{2}\). Then \(\gamma_{2\times}(G_{1}\star G_{2})=3\).
Proof. Let \(\{v_{i};1\le i\le n_{1}\}\) be the vertices of \(G_{1}\) and let \(v_{i}, v_{j}\) for any \(i,j;1\le i,j\le n_{1};i\ne j\) be the two universal vertices. Observe that every vertex of each copy of \(G_{2}\) is adjacent to two universal vertices of \(G_{1}\) in \(G_{1}\star G_{2}\). But the vertices in the copy of \(G_{2}\) with respect to the universal vertices are adjacent to only one vertex of \(G_{1}\). Note that every vertex of \(G_{1}\star G_{2}\) are dominated at least twice by the universal vertices itself but the vertices in the copy of \(G_{2}\) with respect to the two universal vertices are dominated only once by the universal vertices. Consider the set \(S=\{v_{i},v_{j},v_{k};1\le i,j,k\le n_{1};i\ne j\ne k\}\) where \(v_{i}\) and \(v_{j}\) are two universal vertices and \(v_{k}\) is any vertex of \(G_{1}\) which is included in \(S\) to double dominate the vertices in the copy of \(G_{2}\) with respect to the universal vertices. This set dominates every vertex of \(G_{1}\star G_{2}\) at least twice. Therefore, \(S\) is a double dominating set of \(G_{1}\star G_{2}\) which is minimum. Hence, \(\gamma_{2\times}(G_{1}\star G_{2})=|S|=3\). ◻
Theorem 3.6. Let \(G_{1}\) be a cycle of order \(n_{1}\) and \(G_{2}\) be any graph of order \(n_{2}\). Then \(\gamma_{2\times}(G_{1}\star G_{2})=n_{1}\).
Proof. Let \(G_{1}\) be a cycle of order \(n_{1}\) and \(G_{2}\) be any graph of order \(n_{2}\). Let \(\{v_{i};1\le i\le n_{1}\}\) be the vertices of \(G_{1}\). Observe that every vertex of \(i^{th}\) copy of \(G_{2}\) is adjacent to exactly two vertices of \(G_{1}\). Consider the set \(S=\{v_{1},v_{2},\cdots,v_{n_{1}}\}\). This set dominates every vertex of \(G_{1}\star G_{2}\) at least twice. Therefore, \(S\) is a double dominating set of \(G_{1}\star G_{2}\). It is clear that \(S\) is minimum because, to dominate every vertex of each copy of \(G_{2}\) at least twice we need to include one of their neighbors from \(G_{1}\) and minimum dominating set of each copy of \(G_{2}\) or minimum double dominating set of each copy of \(G_{2}\). In both the cases \(\gamma_{2\times}(G_{1}\star G_{2})\ge n_{1}=|S|\). Hence, \(\gamma_{2\times}(G_{1}\star G_{2})=|S|=n_{1}\). ◻
Theorem 3.7. Let \(G_{1}\) be a path graph of order \(n_{1}\) and \(G_{2}\) be a graph of order \(n_{2}\). Then \(\gamma_{2\times}(G_{1}\star G_{2})=n_{1}+2\gamma(G_{2})\).
Proof. The proof is similar to the proof of previous theorem. Let \(G_{1}\) be a path graph of order \(n_{1}\) and \(G_{2}\) be any graph of order \(n_{2}\). Let \(\{v_{i};1\le i\le n_{1}\}\) be the vertices of \(G_{1}\) where \(v_{1}\) and \(v_{n}\) are the pendant vertices of \(G_{1}\). Observe that every vertex of \(i^{th}\) copy of \(G_{2}\) is adjacent to exactly two vertices of \(G_{1}\) except the first and last copy of \(G_{2}\) which are adjacent to only one vertex of \(G_{1}\). Consider the set \(S=\{v_{1},v_{2},\cdots,v_{n_{1}}\}\). This set dominates every vertex of \(G_{1}\star G_{2}\) at least twice but the vertices in first and last copy of \(G_{2}\) are dominated only once by \(S\). In order to double dominate them we include the minimum double dominating sets of first and last copies of \(G_{2}\) to \(S\). This set \(S\) will dominate every vertex of \(G_{1}\star G_{2}\) at least twice. Thus \(S\) is a double dominating set of \(G_{1}\star G_{2}\). This set \(S\) is minimum because to dominate every vertex of each copy of \(G_{2}\) at least twice we need to include one of their neighbors from \(G_{1}\) and minimum dominating set of each copy of \(G_{2}\) or minimum double dominating set of each copy of \(G_{2}\). In both the cases, \(\gamma_{2\times}(G_{1}\star G_{2})\ge n_{1}+2\gamma(G_{2})=|S|\).
Hence, \(\gamma_{2\times}(G_{1}\star G_{2})=|S|=n_{1}+2\gamma(G_{2})\). ◻
Theorem 3.8. Let \(G_{1}\) be a complete bipartite graph of order \(m+n\); \(m,n\ge2\) and \(G_{2}\) be any graph of order \(n'\). Then \(\gamma_{2\times}(G_{1}\star G_{2})=4\).
Proof. Let \(G_{1}\) be a complete bipartite graph of order \(m+n\) and \(G_{2}\) be any graph of order \(n'\). Then \(G_{1}\star G_{2}\) has \((m+n)+(m+n)n'\) vertices. Observe that every vertex of each copy of \(G_{2}\) is adjacent to at least m vertices of \(G_{1}\). Let \(\{v_{1},v_{2},\cdots,v_{m},u_{1},u_{2},\cdots,u_{n}\}\) be the vertices of \(G_{1}\). Then \(G_{2,1},G_{2,2},\cdots,G_{2,m},G_{2,1},\cdots,G_{2,n}\) are the \(m+n\) copies of \(G_{2}\) in \(G_{1}\star G_{2}\). Observe that every vertex of \(G_{2,i}; \forall i, 1\le i\le m\) is adjacent to \(n\) vertices of \(G_{1}\) and every vertex of \(G_{2,i}; \forall i, 1\le i\le n\) is adjacent to \(m\) vertices of \(G_{1}\) in \(G_{1}\star G_{2}\). Let \(S=\{v_{i},v_{j},u_{k},u_{l}\}\) for any \(i,j|i\ne j; 1\le i,j\le m\) and for any \(k,l|1\le k,l\le n;k\ne l\). This set dominates every vertex of \(G_{1}\star G_{2}\) at least twice. Therefore, \(S\) is a double dominating set of \(G_{1}\star G_{2}\) which is minimum.
Hence, \(\gamma_{2\times}(G_{1}\star G_{2})=|S|=4\). ◻
Theorem 3.9. Let \(G_{1}\) be a wheel graph of order \(n_{1}+1\) and \(G_{2}\) be any graph of order \(n_{2}\). Then \(\gamma_{2\times}(G_{1}\star G_{2})=\left\lceil \frac{n_{1}}{2}\right\rceil +1\).
Proof. Let \(G_{1}\) be a wheel graph of order \(n_{1}+1\) and \(G_{2}\) be any graph of order \(n_{2}\). Then \(G_{1}\star G_{2}\) has \((n_{1}+1)+(n_{1}+1)n_{2}\) vertices. Let \(u\) be the universal vertex of \(G_{1}\). Here, every vertex of each copy of \(G_{2}\) has at least three neighbors in \(G_{1}\) in \(G_{1}\star G_{2}\). Also, \(u\) is the common neighbor to every vertex of each copy of \(G_{2}\) except the copy of \(G_{2}\) corresponding to \(u\) in \(G_{1}\star G_{2}\). Let \(\{u,v_{1},v_{n},\cdots,v_{n_{1}}\}\) be the vertices of \(G_{1}\). Consider the set \(S=\{u,v_{i},v_{i+1}\forall i=2k+1;k=0,2,…,\lfloor \frac{n_{1}}{2}\rfloor\}\). This set dominates every vertex of \(G_{1}\star G_{2}\) at least twice. Therefore, \(S\) is a double dominating set of \(G_{1}\star G_{2}\) and \(|S|=1+\left\lceil \frac{n_{1}}{2}\right\rceil\). Now we need to prove \(S\) is minimum. From the definition of double domination number \(\gamma_{2\times}(G_{1}\star G_{2})\le \left\lceil\frac{n_{1}}{2}\right\rceil+1\). The vertex \(v_{n}\) dominates every vertex of \(G_{1}\star G_{2}\) exactly once except the copy of \(G_{2}\) corresponding to \(v_{n}\). The vertices in copies of \(G_{2}\) corresponding to the vertices \(v_{i};1\le i\le n-1\) is adjacent to exactly two vertices other than \(v_{n}\). To dominate them at least twice we need to include for each copy of \(G_{2}\), a vertex \(v_{i};1\le i\le n-1\). Also, observe that two copies of \(G_{2}\) have exactly one common neighbor. This implies, to dominate every vertex of each copy of \(G_{2}\) at least twice, we need at least \(\left\lceil\frac{n_{1}}{2}\right\rceil+1\) vertices. Thus, \(\gamma_{2\times}(G_{1}\star G_{2})\ge \left\lceil\frac{n_{1}}{2}\right\rceil+1\). Therefore, \(S\) is a minimum double dominating set of \(G_{1}\star G_{2}\). Hence, \(\gamma_{2\times}(G_{1}\star G_{2})=|S|=\left\lceil \frac{n_{1}}{2}\right\rceil +1\). ◻
Let \(G_1\) and \(G_2\) be two vertex disjoint graphs of order \(n_{1}\) and \(n_{2}\) and size \(m_{1}\) and \(m_{2}\) respectively. Let \(I(G)\) be the new vertices added in the \(S(G)\) to divide each edge of \(G\). The subdivision-vertex corona of \(G_1\) and \(G_2\), denoted by \(G^{(S)}_1 \odot G_2\), is the graph obtained from \(S(G_1)\) and \(|V(G_1)|\) copies of \(G_2\), all vertex disjoint, and joining the \(i^{th}\) vertex of \(G_1\) to every vertex in the \(i^{th}\) copy of \(G_2\). The subdivision-edge corona of \(G_1\) and \(G_2\), denoted by \(G^{(S)}_1 \circleddash G_2\), is the graph obtained from \(S(G_1)\) and \(m_{1}\) copies of \(G_2\), all vertex disjoint, and joining the \(i^{th}\) vertex of \(I(G_{1})\) to every vertex in the \(i^{th}\) copy of \(G_2\), where \(I(G_1)\) is the set of new vertices added to \(S(G_1)\). The subdivision-vertex neighborhood corona of \(G_1\) and \(G_2\), denoted by \(G^{(S)}_1\boxdot G_2\), is the graph obtained from \(S(G_1)\) and \(|V(G_1)|\) copies of \(G_2\), all vertex disjoint, and joining the neighbors of the \(i^{th}\) vertex of \(G_1\) to every vertex in the \(i^{th}\) copy \(G_2\).
The subdivision-edge neighborhood corona of \(G_1\) and \(G_2\), denoted by \(G^{(S)}_1 \boxminus G_2\), is the graph obtained from \(S(G_1)\) and \(m_{1}\) copies of \(G_2\), all vertex disjoint, and joining the neighbors of the \(i^{th}\) vertex of \(I(G_1)\) to every vertex in the \(i^{th}\) copy of \(G_2\). Figure 7 show the examples of Subdivision vertex corona, Subdivision- edge corona, subdivision vertex neighbourhood corona and subdivision edge neighbourhood corona of graphs \(C_4\) and \(P_2\).
Theorem 4.1. Let \(G_{1}\) and \(G_{2}\) be two graphs of order \(n_{1}\) and \(n_{2}\) respectively. Then \(\gamma_{2\times}(G_{1}^{(S)}\odot G_{2})=n_{1}(1+\gamma(G_{2}))\).
Proof. Let \(\{v_{i};1\le i\le n_{1}\}\) be the vertices of \(G_{1}\). Let \(S\) be the double dominating set of \(G_{1}^{(S)}\odot G_{2}\). Consider the set \(S_{1}=\{v_{i};1\le i\le n_{1}\}\). This set \(S_{1}\) will dominate every vertex in \(I(G_{1})\) exactly twice but the vertices of \(G_{1}\) and the vertices in each copy of \(G_{2}\) is dominated only once by \(S_{1}\). Since every \(i^{th}\) vertex of \(G_{1}\) is adjacent to every vertex in the \(i^{th}\) copy of \(G_{2}\), we include the minimum dominating set \(\{D_{i};1\le i\le n_{1}\}\) of each copy of \(G_{2}\) in \(S\) to double dominate every vertex of \((G_{1}^{(S)}\odot G_{2})\). Therefore, the set \(S=\{S_{1}\cup D_{i};1\le i\le n_{1}\}\) will dominate every vertex of \(G_{1}^{(S)}\odot G_{2}\) at least twice and \(S\) is a double dominating set and \(|S|=n_{1}(\gamma(G_{2})+1)\). Now we need to prove \(S\) is the minimum double dominating set. Observe that every vertex in \(I(G_{1})\) is adjacent to exactly two vertices of \(G_{1}\) and every vertex in the each copy of \(G_{2}\) is adjacent to exactly one vertex of \(G_{1}\). To dominate them at least twice we need to include either both the neighbors of vertices in \(I(G_{1})\) and the minimum dominating set of each copy of \(G_{2}\) or every vertex in \(I(G_{1})\) and one of their neighbors and minimum double dominating set of each copy of \(G_{2}\). In both the cases \(\gamma_{2\times}(G_{1}^{(S)}\odot G_{2})\ge |S|=n_{1}(\gamma(G_{2})+1)\). This proves \(S\) is the minimum double dominating set of \((G_{1}^{(S)}\odot G_{2})\). Hence, \(\gamma_{2\times}(G_{1}^{(S)}\odot G_{2})=n_{1}(1+\gamma(G_{2}))\). ◻
Theorem 4.2. Let \(G_{1}\) and \(G_{2}\) be two graphs of order \(n_{1}\) and \(n_{2}\) and of size \(m_{1}\) and \(m_{2}\) respectively. Then \[\gamma_{2\times}(G_{1}^{(S)}\circleddash G_{2}) = \begin{cases} m_{1}(\gamma(G_{2})+1)+l_{1};\quad \text{if $\delta(G_{1})=1$},\\ m_{1}(\gamma(G_{2})+1); \quad \text{otherwise}, \end{cases}\] where \(l_{1}\) is the number of leaves in \(G_{1}\)
Proof. The proof is similar to the proof of previous theorem.
Case 1. When \(\delta(G)\ge2\), in \((G_{1}^{(S)}\circleddash G_{2})\) every vertex in each copy of \(G_{2}\) is adjacent to exactly one vertex of \(I(G_{1})\). Let \(S\) be the double dominating set of \((G_{1}^{(S)}\circleddash G_{2})\). Let \(I(G_{1})\subseteq S\). Now \(S\) dominates every vertex of \(G_{1}\) at least twice but the vertices in \(I(G_{1})\) and the vertices of each copy of \(G_{2}\) is dominated only once by \(S\). Since every \(i^{th}\) vertex of \(I(G_{1})\) is adjacent to every vertex of \(i^{th}\) copy of \(G_{2}\), we include the minimum dominating set \(\{D_{i};1\le i\le m_{1}\}\) of each copy of \(G_{2}\) in \(S\) to double dominate every vertex of \((G_{1}^{(S)}\circleddash G_{2})\) at least twice and thus \(S=I(G_{1})\cup D_{i}\) for \(1\le i\le n\) is a double dominating set of \((G_{1}^{(S)}\circleddash G_{2})\) which is minimum. Hence, \(\gamma_{2\times}(G_{1}^{(S)}\circleddash G_{2})=m_{1}(\gamma(G_{2})+1)\).
Case 2. When \(\delta(G_{1})=1\), a pendant vertex of \(G_{1}\) remains as a pendant vertex in \((G_{1}^{(S)}\circleddash G_{2})\). Therefore, the set \(S=I(G_{1})\cup D_{i}\) for \(1\le i\le n\) dominates every vertex of \((G_{1}^{(S)}\circleddash G_{2})\) at least twice, but the pendant vertices are dominated only once by \(S\). By observation 1, we need to include all the pendant vertices to \(S\). Hence, \(\gamma_{2\times}(G_{1}^{(S)}\circleddash G_{2}) = m_{1}(\gamma_{2\times(G)}+1)+l_{1}\) where, \(l_{1}\) is the number of pendant vertices in \(G_{1}\). ◻
Theorem 4.3. Let \(G_{1}\) be a graph of order \(n_{1}\) whose vertices are either a pendant vertex or a support vertex and \(G_{2}\) be a graph of order \(n_{2}\). Then \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_{2})=m_{1}+l(1+\gamma(G_{2}))\) where \(l\) is the number of pendant vertices in \(G_{1}\).
Proof. In \(G^{(S)}_{1}\boxdot G_2\) the pendant vertices of \(G_{1}\) remain as pendant vertices. Let \(\{v_{i};1\le i\le n_{1}\}\) be the vertices of \(G_{1}\) and \(\{u_{j};1\le j\le m_{1}\}\) be the vertices of \(I(G_{1})\). Consider the set \(S=\{u_{j},v_{k};1\le j\le m_{1};1\le k\le l\}\). This set dominates every vertex of \(G^{(S)}_{1}\boxdot G_{2}\) at least twice. Therefore, \(S\) is the double dominating set of \(G^{(S)}_{1}\boxdot G_{2}\). Now we need to prove \(S\) is minimum. From the definition of double domination number, \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_{2})\le |S|\). By Observation 1.1, we need to include all the pendant vertices and support vertices of \(G^{(S)}_{1}\boxdot G_{2}\) in the double dominating set. This dominates every vertex of \(G^{(S)}_{1}\boxdot G_{2}\) at least twice but the vertices in copies of \(G_{2}\) corresponding to the pendant vertices are dominated only once by \(S\). To dominate them at least twice we need to include the minimum dominating set of each copy of \(G_{2}\) corresponding to the pendant vertices. Hence, \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_{2})=m_{1}+l(1+\gamma(G_{2}))\). ◻
Theorem 4.4. Let \(G_{1}\) be a cycle graph of order \(n_{1}\) and size \(m_{1}\) and \(G_{2}\) be a graph of order \(n_{2}\) and size \(m_{2}\). Then \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_2) = m_{1}+\left\lceil \frac{n_{1}}{2}\right\rceil\).
Proof. In \(G^{(S)}_{1}\boxdot G_2\) every vertex in each copy of \(G_{2}\) is adjacent to exactly two vertices of \(G_{1}\). Let \(S\) be the double dominating set of \(G^{(S)}_{1}\boxdot G_2\). Let \(I(G_{1})\subseteq S\). Now \(S\) dominates every vertex of \(G^{(S)}_{1}\boxdot G_2\) at least twice but the vertices in \(I(G_{1})\) are dominated only once by \(S\). Let \(\{u_{j};1\le j\le m_{1}\}\) be the vertices in \(I(G_{1})\) and \(\{v_{i};1\le i\le n_{1}\}\) be the vertices of \(G_{1}\). Each vertex in \(I(G_{1})\) has exactly two neighbors in \(G_{1}\) and two consecutive vertices \(u_{i},u_{i+1}\) of \(I(G_{1})\) have exactly one common neighbor. Therefore, to dominate the vertices in \(I(G_{1})\) at least twice we include the vertices \(\{v_{i}; i\equiv 1\mod 2; 1\le i\le n_{1}\}\) to \(S\). Thus the set \(S=I(G_{1})\cup\{v_{i};i\equiv 1\mod2; 1\le i\le n_{1}\}\) is a double dominating set of \(G^{(S)}_{1}\boxdot G_2\) which is minimum. Hence, \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_2) =|S|= m_{1}+\left\lceil \frac{n_{1}}{2}\right\rceil\). ◻
Theorem 4.5. Let \(G_{1}\) be a path graph of order \(n_{1}\) and size \(m_{1}\) and \(G_{2}\) be a graph of order \(n_{2}\) and size \(m_{2}\). Then \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_2) = m_{1}+\left\lceil \frac{n_{1}}{2}\right\rceil + 2\gamma(G_{2})\).
Proof. The proof is similar to the previous theorem. In \(G^{(S)}_{1}\boxdot G_2\) every vertex in each copy of \(G_{2}\) is adjacent to exactly two vertices of \(G_{1}\) but the two copies of \(G_{2}\) corresponding to the pendant vertices of \(G_{1}\) is adjacent to only one vertex of \(G_{1}\). Let \(v_{1}\) and \(v_{n_{1}}\) be the pendant vertices of \(G_{1}\) and \(G_{2}^{(v_{1})}\) and \(G_{2}^{(v_{n_{1}})}\) be the copies of \(G_{2}\) corresponding to the pendant vertices respectively. Let \(S\) be the double dominating set of \(G^{(S)}_{1}\boxdot G_2\). Let \(I(G_{1})\subseteq S\). Now \(S\) dominates every vertex of \(G^{(S)}_{1}\boxdot G_2\) at least twice but the vertices in \(I(G_{1})\) and vertices in \(G_{2}^{(v_{1})}\) and \(G_{2}^{(v_{n_{1}})}\) are dominated only once by \(S\). Let \(\{u_{i};1\le i\le m_{1}\}\) be the vertices in \(I(G_{1})\) and \(\{v_{i};1\le i\le n_{1}\}\) be the vertices of \(G_{1}\). To dominate the vertices in \(I(G_{1})\) and vertices in \(G_{2}^{(v_{1})}\) and \(G_{2}^{(v_{n_{1}})}\) at least twice, we include the vertices \(\{v_{i}; i\equiv1\mod2; 1\le i\le n_{1}\}\) and the minimum dominating sets \(D_{1}\) and \(D_{n_{1}}\) of \(G_{2}^{(v_{1})}\) and \(G_{2}^{(v_{n_{1}})}\) to \(S\). Thus the set \(S=I(G_{1})\cup\{v_{i};1\le i\le \left\lceil\frac{n_{1}}{2}\right\rceil\}\cup D_{1}\cup D_{n_{1}}\) is a double dominating set of \(G^{(S)}_{1}\boxdot G_2\) which is minimum. Hence, \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_2) =|S|= m_{1}+\left\lceil \frac{n_{1}}{2}\right\rceil+2\gamma(G)\). ◻
Theorem 4.6. Let \(G_{1}\) be a wheel graph of order \(n_{1}\) and size \(m_{1}\) and \(G_{2}\) be a graph of order \(n_{2}\) and size \(m_{2}\). Then \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_2) = \frac{m_{1}}{2}+\left\lceil \frac{n_{1}-1}{2}\right\rceil + \lfloor \frac{n_{1}-1}{2}\rfloor+1\).
Proof. In \(G^{(S)}_{1}\boxdot G_2\), every vertex in each copy of \(G_{2}\) is adjacent to exactly three vertices of \(G_{1}\). Let \(\{v_{i};1\le i\le n_{1}\}\) be the vertices of \(G_{1}\) where \(v_{n_{1}}\) is the universal vertex of \(G_{1}\). Let \(\{u_{j};1\le j\le m_{1}\}\) be the vertices in \(I(G_{1})\) where \(\{u_{j};1\le j\le \frac{m_{1}}{2}\}\) are the vertices corresponding to the edges in the outer cycle of \(G_{1}\) and \(\{u_{j};\frac{m_{1}}{2}+1 \le j\le m_{1}\}\) be the vertices corresponding to the edges inside the cycle of \(G_{1}\). Consider the set \(S=\{u_{j},v_{i};1\le i\le \frac{m_{1}}{2};i\equiv0\mod2;1\le i\le n_{1}-1\}\cup\{u_{j};\frac{m_{1}}{2}+1\le j\le m_{1};j\equiv1\mod{2}\}\cup\{v_{n_{1}}\}\). This set \(S\) dominates every vertex of \(G^{(S)}_{n_1}\boxdot G_2\) at least twice. Thus \(S\) is a double dominating set of \(G^{(S)}_{n_1}\boxdot G_2\). Now we need to prove \(S\) is the minimum double dominating set. Observe that the vertices in each copy of \(G_{2}\) are adjacent to the vertices in \(I(G_{1})\) only. Also, the every vertex of \(I(G_{1})\) is adjacent to exactly two vertices in \(G_{1}\). Therefore, to dominate the vertices of \(I(G_{1})\) and every vertex of each copy of \(G_{2}\) at least twice we need to include every vertex of \(I(G_{1})\) and one of the neighbors of each vertex in \(I(G_{1})\) or both the neighbors of each vertex of \(I(G_{1})\) and the minimum double dominating set of each copy of \(G_{2}\). In both the cases \(\gamma_{2\times}(G^{(S)}_{n_1}\boxdot G_2)\ge |S|= \frac{m_{1}}{2}+\left\lceil \frac{n_{1}-1}{2}\right\rceil + \lfloor \frac{n_{1}-1}{2}\rfloor+1\). Hence, \(S\) is the minimum double dominating set and \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_2) = \frac{m_{1}}{2}+\left\lceil \frac{n_{1}-1}{2}\right\rceil + \lfloor \frac{n_{1}-1}{2}\rfloor+1\). ◻
Theorem 4.7. Let \(G_{1}\) be a complete graph of order \(n_{1}\) and size \(m_{1}\) and \(G_{2}\) be a graph of order \(n_{2}\) and size \(m_{2}\). Then \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_2) = 2n_{1}\).
Proof. Let \(\{v_{i};1\le i\le n_{1}\}\) be the vertices of \(G_{1}\) and \(\{u_{j};1\le j\le m_{1}\}\) be the vertices in \(I(G_{1})\) where \(\{u_{j};1\le j\le n_{1}\}\) be the vertices dividing the edges in outer cycle of \(G_{1}\). Consider the set \(S=\{v_{i},u_{j};1\le i\le n_{1};1\le j\le n_{1}\}\). This set dominates every vertex of \(G^{(S)}_{1}\boxdot G_2\) at least twice. Therefore, \(S\) is a double dominating set of \(G^{(S)}_{1}\boxdot G_2\). We need to prove \(S\) is minimum. In \(G^{(S)}_{1}\boxdot G_2\), every vertex in each copy of \(G_{2}\) is adjacent to exactly \(n-1\) vertices of \(I(G_{1})\) and each vertex in \(I(G_{1})\) is adjacent to exactly two neighbors of \(G_{1}\). Observe that every vertex dividing the edges inside of the cycle \(\{u_{j};n_{1}+1\le j\le m_{1}\}\) share no common vertices of \(G_{1}\). To dominate every vertex of \(G^{(S)}_{1}\boxdot G_2\) at least twice we need to include either two of the neighbors of copies of \(G_{2}\) from \(I(G_{1})\) and two neighbors of \(\{u_{j};n_{1}+1\le j\le m_{1}\}\) or two of the neighbors of copies of \(G_{2}\) from \(I(G_{1})\) and the vertices \(\{u_{j};n_{1}+1\le j\le m_{1}\}\) and one of their neighbors from \(G_{1}\). In both the cases, \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_2)\ge 2n_{1}=|S|\). Hence \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_2) = 2n_{1}\). ◻
Theorem 4.8. Let \(G_{1}\) be a complete bipartite graph of order \(n_{1}+n_{2}\) and size \(m_{1}\) and \(G_{2}\) be a graph of order \(n_{3}\) and size \(m_{2}\). Then \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_2) = n_{1}n_{2}+min\{n_{1},n_{2}\}\).
Proof. Let \(\{v_{i};1\le i\le n_{1}+n_{2}\}\) be the vertices of \(G_{1}\) and \(\{u_{j};1\le j\le m_{1}\}\) be the vertices in \(I(G_{1})\). Consider the set \(\{u_{j};1\le j\le m_{1}\}\). This set of vertices will dominate every vertex of each copy of \(G_{2}\) at least twice but the vertices \(\{u_{j}, v_{i};1\le j\le m_{1};1\le i\le n_{1}+n_{2}\}\) are dominated only once by \(I(G_{1})\). Now consider the set \(S=\{v_{i},u_{j};1\le i\le min\{n_{1},n_{2}\}\}\). This set will dominate every vertex of \(G^{(S)}_{1}\boxdot G_2\) at least twice. Therefore, \(S\) is the double dominating set of \(G^{(S)}_{1}\boxdot G_2\). We need to prove \(S\) is minimum. From definition of double domination number, \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_{2})\le|S|=n_{1}n_{2}+min\{n_{1},n_{2}\}\). In \(G^{(S)}_{1}\boxdot G_{2}\), the vertices in \(I(G_{1})\) are adjacent to exactly two vertices of \(G_{1}\). To dominate these vertices at least twice we need to include all the vertices in \(I(G_{1})\) and one of their neighbors or both the neighbors of \(I(G_{1})\). In first case, those vertices dominates every vertex of \(G^{(S)}_{1}\boxdot G_{2}\) at least twice, but in the latter case, only the vertices of \(I(G_{1})\) are dominate twice and remaining vertices are not dominated at least twice. Therefore, we need to include two of the vertices from \(I(G_{1})\) for each copy of \(G_{2}\). In both the cases, \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_{2})\ge n_{1}n_{2}+min\{n_{1},n_{2}\}=|S|\). Hence, \(\gamma_{2\times}(G^{(S)}_{1}\boxdot G_2) = n_{1}n_{2}+min\{n_{1},n_{2}\}\). ◻
Theorem 4.9. Let \(G_{1}\) and \(G_{2}\) be the two graphs of order \(n_{1}\) and \(n_{2}\) respectively. Then \(\gamma_{2\times}(G^{(S)}_{n_1}\boxminus G_2)=n_{1}+\left\lceil\frac{n_{1}}{2}\right\rceil\).
Proof. Let \(\{v_{i};1\le i\le n_{1}\}\) be the vertices of \(G_{1}\) and \(\{u_{j};1\le j\le m_{1}\}\) be the vertices of \(I(G_{1})\). In \(G^{(S)}_{n_1}\boxminus G_2\) every vertex in each copy of \(G_{2}\) is adjacent to exactly two vertices of \(G_{1}\). Consider the set \(S=\{v_{i};1\le i\le n_{1}\}\). This set dominates every vertex of \((G^{(S)}_{n_1}\boxminus G_2)\) at least twice except the vertices of \(G_{1}\). In order to dominate them at least twice we include the vertices \(\{u_{j};j\equiv1\mod2; 1\le j\le m_{1}\}\) to \(S\). Thus the set \(S=\{v_{i},u_{j};1\le i\le n_{1};1\le j\le m_{1};j\equiv1\mod2\}\) dominates every vertex of \((G^{(S)}_{n_1}\boxminus G_2)\) at least twice. This \(S\) is the minimum double dominating set because every vertex of each copy of \(G_{2}\) and \(I(G_{1})\) are adjacent to exactly two vertices of \(G_{1}\). But the vertices of \(G_{1}\) are adjacent to exactly one vertex of \(I(G_{1})\) and adjacent to the vertices of \(G_{2}\). To dominate them we have to include one of the neighbors of the vertices of \(G_{1}\). Since, two vertices of \(G_{1}\) have a common neighbor from \(I(G_{1})\) to dominate them at least twice, we need to include at least \(\left\lceil\frac{n_{1}}{2}\right\rceil\) vertices from \(I(G_{1})\). This implies, \(\gamma_{2\times}(G^{(S)}_{n_1}\boxminus G_2)\ge n_{1}+\left\lceil\frac{n_{1}}{2}\right\rceil=|S|\). Hence, \(\gamma_{2\times}(G^{(S)}_{n_1}\boxminus G_2)=|S|=n_{1}+\left\lceil\frac{n_{1}}{2}\right\rceil\). ◻
Theorem 4.10. Let \(G_{1}\) be a graph of order \(n_{1}\) where every vertex of \(G_{1}\) is either a pendant or a support vertex and \(G_{2}\) be a graph of order \(n_{2}\). Then \(\gamma_{2\times}(G^{(S)}_{n_1}\boxminus G_2)=n_{1}+l\) where \(l\) is the number of pendant vertices in \(G_{1}\).
Proof. In \(G^{(S)}_{n_1}\boxminus G_2\), every vertex in each copy of \(G_{2}\) is adjacent to exactly two vertices of \(G_{1}\). Let \(S=\{v_{i};1\le i\le n_{1}\}\). This set dominates every vertex of \(G^{(S)}_{n_1}\boxminus G_2\) at least twice except the vertices of \(G_{1}\). Let \(\{e_{j};1\le j\le l\}\) be the pendant edges of \(G_{1}\) and \(\{u_{j};1\le j\le l\}\) be the vertices of \(I(G_{1})\) corresponding to the pendant edges. In order to dominate the vertices of \(G_{1}\) at least twice we include the vertices \(\{u_{j};1\le j\le l\}\) to \(S\) because these vertices are adjacent to both pendant and support vertices of \(G_{1}\). Therefore, the set \(S=\{v_{i}, u_{j};1\le i\le n_{1};1\le j\le l\}\) is a double dominating set which is also minimum. Hence, \(\gamma_{2\times}(G^{(S)}_{n_1}\boxminus G_2)=|S|=n_{1}+l\). ◻
Let \(G_1\) and \(G_2\) be two vertex disjoint graphs. The \(R\)-vertex corona of \(G_1\) and \(G_2\), denoted by \(G^{(R)}_1 \odot G_2\), is the graph obtained from vertex disjoint \(R(G_1)\) and \(V(G_1)\) copies of \(G_2\) by joining the \(i^{th}\) vertex of \(G_1\) to every vertex in the \(i^{th}\) copy of \(G_2\) . The \(R\)-edge corona of \(G_1\) and \(G_2\), denoted by \(G^{(R)}_1 \circleddash G_2\), is the graph obtained from vertex disjoint \(R(G_1)\) and \(I(G_1)\) copies of \(G_2\) by joining the \(i^{th}\) vertex of \(I(G_1)\) to every vertex in the \(i^{th}\) copy of \(G_2\), where \(I(G_1) = V(R(G_1)) -V(G_1)\). The \(R\)-vertex neighborhood corona of \(G_1\) and \(G_2\), denoted by \(G^{(R)}_1 \boxdot G_2\), is the graph obtained from vertex disjoint \(R(G_1)\) and \(V(G_1)\) copies of \(G_2\) by joining the neighbors of the \(i^{th}\) vertex of \(G_1\) in \(R(G_1)\) to every vertex in the \(i^{th}\) copy of \(G_2\). The \(R\)-edge neighborhood corona of \(G_1\) and \(G_2\), denoted by \(G^{(R)}_1 \boxminus G_2\), is the graph obtained from vertex disjoint \(R(G_1)\) and \(I(G_1)\) copies of \(G_2\) by joining the neighbors of the \(i^{th}\) vertex of \(I(G_1)\) in \(R(G_1)\) to every vertex in the \(i^{th}\) copy of \(G_2\). Figure 8 show the examples of R-vertex corona, R-edge corona, R-vertex neighbourhood corona, R-edge neighbourhood corona of graphs \(C_4\) and \(P_2\).
Theorem 5.1. Let \(G_{1}\) and \(G_{2}\) be two graphs of order \(n_{1}\) and \(n_{2}\) respectively. Then \(\gamma_{2\times}(G^{(R)}_{1}\odot G_2)=n_{1}(1+\gamma(G_{2}))\).
Proof. Let \(\{v_{i},u_{j};1\le i\le n_{1};1\le j \le m_{1}\}\) be the vertices of \(G_{1}^{(R)}\). Consider the set \(S=\{v_{i};1\le i\le n_{1}\}\). This set dominates every vertex of \((G^{(R)}_{1}\odot G_2)\) at least twice, but the vertices in \(G_{1}\) and vertices in each copy of \(G_{2}\) are dominated only once by \(S\). In order to double dominate them we include minimum dominating set \(D_{i};1\le i\le n_{1}\) of each copy of \(G_{2}\) to \(S\). Therefore, the set \(S=\{v_{i};1\le i\le n_{1}\}\cup \{D_{i};1\le i\le n_{1}\}\) dominates every vertex of \(G^{(R)}_{1}\odot G_2\) at least twice and thus a double dominating set of \(G^{(R)}_{1}\odot G_2\). This set \(S\) is a minimum double dominating set because, each \(u_{j}\) is adjacent to exactly two vertices of \(G_{1}\). In \((G^{(R)}_{1}\odot G_2)\) every vertex of each copy of \(G_{2}\) is adjacent to exactly one vertex of \(G_{1}\). The vertices of \(I(G_{1})\) are dominated exactly twice by \(S\) but the vertices in each copy of \(G_{2}\) are dominated only once by \(S\). In order to dominate them at least twice, we need to include the neighbors of those vertices from \(G_{1}\) and the minimum dominating set of each copy of \(G_{2}\). Hence, \(\gamma_{2\times}(G^{(R)}_{1}\odot G_2)=n_{1}(1+\gamma(G_{2}))\). ◻
Theorem 5.2. Let \(G_{1}\) and \(G_{2}\) be two graphs of order \(n_{1}\) and \(n_{2}\) and size \(m_{1}\) and \(m_{2}\) respectively. Then \[\gamma_{2\times}(G_{1}^{(R)}\circleddash G_{2}) = \begin{cases} m_{1}(\gamma(G_{2})+1)+s_{1};\quad \text{if $\delta(G_{1})=1$},\\ m_{1}(\gamma(G_{2})+1); \quad \text{otherwise}, \end{cases}\] where \(s_{1}\) is the number of support vertices in \(G_{1}\).
Proof. Case 1. When \(\delta(G_{1})\ge 2\).
The proof is similar to the previous theorem. Let \(\{v_{i},u_{j};1\le i\le n_{1};1\le j \le m_{1}\}\) be the vertices of \(G_{1}^{(R)}\). Consider the set \(S=\{u_{j};1\le i\le m_{1}\}\). This set dominates every vertex of \((G^{(R)}_{1}\odot G_2)\) at least twice, but the vertices \(\{u_{j};1\le j\le m_{1}\}\) and vertices in each copy of \(G_{2}\) are dominated only once by \(S\). In order to double dominate them we include minimum dominating set \(D_{i};1\le i\le n_{1}\) of each copy of \(G_{2}\) to \(S\). Therefore, the set \(S=\{u_{j};1\le j\le m_{1}\}\cup \{D_{i};1\le i\le n_{1}\}\) dominates every vertex of \(G^{(R)}_{1}\odot G_2\) at least twice and thus a double dominating set of \(G^{(R)}_{1}\odot G_2\). Now we need to prove \(S\) is minimum. From definition of double domination number \(\gamma_{2\times}(G^{(R)}_{1}\odot G_2)\le |S|\). Observe that each \(u_{j}\) is adjacent to exactly two vertices of \(G_{1}\). In \((G^{(R)}_{1}\odot G_2)\) every vertex of each copy of \(G_{2}\) is adjacent to exactly one vertex of \(I(G_{1})\). To dominate them at least twice we need to include the vertices of \(I(G_{1})\) and the minimum dominating set of each copy of \(G_{2}\). Hence, \(\gamma_{2\times}(G^{(R)}_{1}\odot G_2)=|S|=m_{1}(1+\gamma(G_{2}))\).
Case 2. When \(\delta(G_{1})=1\).
In this case the set \(S=\{u_{j};1\le j\le m_{1}\}\cup \{D_{i};1\le i\le n_{1}\}\) defined in the previous case dominates every vertex of \(G_{1}^{(R)}\circleddash G_{2}\) at least twice but the pendant vertices of \(G_{1}\) are dominated only once by \(S\). Therefore, by observation 1, we include the support vertices of \(G_{1}\) to \(S\). Let \(SP(G_{1})\) be the set of all support vertices of \(G_{1}\). The set \(S=\{u_{j};1\le j\le m_{1}\}\cup \{D_{i};1\le i\le n_{1}\}\cup\{SP(G_{1})\}\) dominates every vertex of \(G_{1}^{(R)}\circleddash G_{2}\) at least twice. Thus \(S\) is a double dominating set of \(G_{1}^{(R)}\circleddash G_{2}\) which is minimum. Hence, \(\gamma_{2\times}(G_{1}^{(R)}\circleddash G_{2})=|S|=m_{1}(1+\gamma(G_{2}))+s_{1}\). ◻
Theorem 5.3. Let \(G_{1}\) and \(G_{2}\) be two graphs of order \(n_{1}\) and \(n_{2}\) respectively. Then \(\gamma_{2\times}(G_{1}^{(R)}\boxdot G_{2})=n_{1}\).
Proof. Let \(\{v_{i},u_{j};1\le i\le n_{1};1\le j\le m_{1}\}\) be the vertices of \(G_{1}^{(R)}\). Consider the set \(S=\{v_{i};1\le i\le n_{1}\}\). This set \(S\) dominates every vertex of \(G_{1}^{(R)}\boxdot G_{2}\) at least twice. Therefore, \(S\) is a double dominating set of \(G_{1}^{(R)}\boxdot G_{2}\). This set \(S\) is the minimum double dominating set because every vertex of \(G_{1}^{(R)}\boxdot G_{2}\) is adjacent to exactly two vertices of \(G_{1}\) and to dominate these vertices at least twice, we need at least \(n_{1}\) vertices. Hence, \(\gamma_{2\times}(G_{1}^{(R)}\boxdot G_{2})=n_{1}\). ◻
Theorem 5.4. Let \(G_{1}\) and \(G_{2}\) be two graphs of order \(n_{1}\) and \(n_{2}\) respectively. Then \(\gamma_{2\times}(G_{1}^{(R)}\boxminus G_{2})=n_{1}\).
Proof. The proof is similar to the previous theorem. Let \(\{v_{i},u_{j};1\le i\le n_{1};1\le j\le m_{1}\}\) be the vertices of \(G_{1}^{(R)}\). Consider the set \(S=\{v_{i};1\le i\le n_{1}\}\). This set \(S\) dominates every vertex of \(G_{1}^{(R)}\boxminus G_{2}\) at least twice. Therefore, \(S\) is a double dominating set of \(G_{1}^{(R)}\boxminus G_{2}\). This set \(S\) is minimum double dominating set because, in \(G_{1}^{(R)}\boxminus G_{2}\) every vertex in each copy of \(G_{2}\) and the vertices \(\{u_{j};1\le j\le m_{1}\}\) are adjacent to exactly two vertices of \(G_{1}\). To double dominate them we need at least \(n_{1}\). Hence, \(\gamma_{2\times}(G_{1}^{(R)}\boxminus G_{2})=n_{1}\). ◻
The impact of unary operations on double domination number of standard graphs is given below:
| Graph class | Operation | \(\gamma_2\times\) |
| \(C_n\) | Inflation | \(\left\lceil\frac{4n}{3}\right\rceil\) |
| \(P_n\) | Inflation | \(\left\lceil\frac{4(n-2)}{3}\right\rceil\) |
| \(W_n\) | Inflation | \(\left\lceil\frac{2(n-1)}{3}\right\rceil+\left\lceil\frac{n-1}{2}\right\rceil\) |
| \(K_n\) | Inflation | \(2(n-1)\) |
| \(K_{m,n}\) | Inflation | \(2(m+n-1)\) |
| \(K_{1,n}\) | Inflaton | \(2l(K_{1,n})\) |
| \(S_{r,t}\) | Inflation | \(2l(S_{r,t})\) |
| Any graph \(G\) | Cubic inflation | \(2m(G)\) |
| \(C_n\) | \(\alpha-\)operation | \(n\) |
| \(P_n\) | \(\alpha-\)operation | \(n-1,n\equiv1\mod3\); \(n\), otherwise |
| \(W_n\) | \(\alpha-\)operation | \(4\) |
| \(K_n\) | \(\alpha-\)operation | \(4\) |
| \(K_{m,n}\) | \(\alpha-\)operation | \(4\) |
| \(K_{1,n}\) | \(\alpha-\)operation | \(4\) |
| \(S_{r,t}\) | \(\alpha-\)operation | \(4\) |
| \(C_n\) | \(\beta-\)operation | \(\left\lceil\frac{2n}{3}\right\rceil\) |
| \(P_n\) | \(\beta-\)operation | \(\left\lceil\frac{2(n+1)}{3}\right\rceil-1,n\equiv1\mod3\); \(\left\lceil\frac{2(n+1)}{3}\right\rceil\), otherwise |
| \(W_n\) | \(\beta-\)operation | \(4\) |
| \(K_n\) | \(\beta-\)operation | \(4\) |
| \(K_{m,n}\) | \(\beta-\)operation | \(4\) |
| \(K_{1,n}\) | \(\beta-\)operation | \(4\) |
| \(S_{r,t}\) | \(\beta-\)operation | \(4\) |
| \(G_1\diamond G_2\) | Edge corona | \(n(G_1)\) |
| \(C_n\star G_2\) | Neighborhood Corona | \(n\) |
| \(P_n\star G_2\) | Neighborhood Corona | \(n+2\gamma(G_2)\) |
| \(W_n\star G_2\) | Neighborhood Corona | \(\left\lceil\frac{n}{2}\right\rceil+1\) |
| \(K_n\star G_2\) | Neighborhood Corona | \(3\) |
| \(K_{m,n}\star G_2\) | Neighborhood Corona | \(4\) |
| \(K_{1,n}\star G_2\) | Neighborhood Corona | \((n+1)+l.\gamma(G_2)\) |
| \(S_{r,t}\star G_2\) | Neighborhood Corona | \((r+t)+l.\gamma(G_2)\) |
| \(G_1^{(S)}\odot G_2\) | Subdivision-vertex corona | \(n_1(1+\gamma(G_2))\) |
| \(G_1^{(S)}\circleddash G_2\) | Subdivision-edge corona | \(m_1(1+\gamma(G_2))+l(G_1);\delta(G_1)=1\); \(m_1(1+\gamma(G_2))\); otherwise |
| \(C_n^{(S)}\boxdot G_2\) | Subdivision-vertex Neighborhood Corona | \(m(C_n)+\left\lceil\frac{n}{2}\right\rceil\) |
| \(P_n^{(S)}\boxdot G_2\) | Subdivision-vertex Neighborhood Corona | \(m(P_n)+\left\lceil\frac{n}{2}\right\rceil+2\gamma(G_2)\) |
| \(W_n^{(S)}\boxdot G_2\) | Subdivision-vertex Neighborhood Corona | \(\frac{m(W_{n})}{2}+\left\lceil \frac{n(W_{n})-1}{2}\right\rceil + \lfloor \frac{n(W_{n})-1}{2}\rfloor+1\) |
| \(K_n^{(S)}\boxdot G_2\) | Subdivision-vertex Neighborhood Corona | \(2n\) |
| \(K_{m,n}^{(S)}\boxdot G_2\) | Subdivision-vertex Neighborhood Corona | \(mn+min\{m,n\}\) |
| \(K_{1,n}^{(S)}\boxdot G_2\) | Subdivision-vertex Neighborhood Corona | \(m(K_{1,2})+l(1+\gamma(G_2))\) |
| \(S_{r,t}^{(S)}\boxdot G_2\) | Subdivision-vertex Neighborhood Corona | \(m(S_{r,t})+l(1+\gamma(G_2))\) |
| \(G_1^{(S)}\boxminus G_2\) | Subdivision-edge Neighborhood Corona | \(n_1+\left\lceil\frac{n_{1}}{2}\right\rceil\) |
| \(K_{1,n}^{(S)}\boxminus G_2\) | Subdivision-edge Neighborhood Corona | \((n+1)+l(K_{1,n})\) |
| \(S_{r,t}^{(S)}\boxminus G_2\) | Subdivision-edge Neighborhood Corona | \((r+t)+l(S_{r,t})\) |
| \((G^{(R)}_1\odot G_2)\) | R-vertex corona | \(n_1(1+\gamma(G_2))\) |
| \((G^{(R)}_1\circleddash G_2)\) | R-edge corona | \(m_1(1+\gamma(G_2))+s_1, \delta(G_1)=1\); \(m_1(1+\gamma(G_2))\); otherwise |
| \((G^{(R)}_1\boxdot G_2)\) | R-vertex neighborhood corona | \(n(G_1)\) |
| \((G^{(R)}_1\boxminus G_2)\) | R-vertex neighborhood corona | \(n(G_1)\) |
This work studies the impact of various unary and binary operations on graphs, including inflation and cubic inflation and various corona operations on double domination number. We also defined two new unary operations and explored the impact of these operations on the double domination number. The inflation and cubic inflation operations increase the order and size of the graph, and thus the double domination number increases. The two new operations defined in this paper also increase the order and size of the graph and thus creates an impact to the double domination number of graphs . Further, we studied the double domination number of various corona operations of two graphs. These findings contribute to the better understanding of double domination in various graph structures.
The first author expresses the gratitude to Vellore Institute of Technology, Vellore for providing financial support that enabled the author to carry out the research.
The authors declare no conflicts of interest.
The authors have equally contributed to this work.