Let \(G = (V, E)\) be a simple graph. A subset \(D \subseteq V\) is called a dominating set of \(G\) if every vertex in \(V\) is either in \(D\) or has a neighbour in \(D\). A subset \(D \subseteq V\) is called an equitable dominating set of \(G\) if for every vertex \(v \in V \setminus D\), there exists a vertex \(u \in D\) such that \(uv \in E(G)\) and \(\lvert d_G(u) – d_G(v) \rvert \leq 1\). The minimum cardinality of an equitable dominating set of \(G\), denoted by \(\gamma^{e}(G)\), is called the equitable domination number of \(G\). In this paper, we study the equitable domination number of certain graph operators such as the double graph, the Mycielskian, and the subdivision of a graph.
The inception of domination in 1960 by Ore and Berge [2, 10] laid the path for the emergence of various research problems in the field of graph theory. A wide range of applications, such as communication network problems and the school bus routing problem, has drawn substantial interest from researchers. Foundational studies by Cockayne [6], Lasker [1], Haynes [7], and others have significantly motivated further research in domination theory.
In this work, we consider only graphs that are finite, simple, connected, and undirected. We adopt the graph-theoretical terminology in [4]. The degree of a vertex \(v\) in a graph \(G\), \(d_{G}(v)\), is the number of edges incident with \(v\). For a vertex \(u\) in a graph \(G\), \(N_{G}(u)\) denotes the set of all neighbours of \(u\). The minimum degree of a vertex in a graph \(G\) is denoted by \(\delta(G)\). The maximum degree of a vertex in a graph \(G\) is denoted by \(\Delta(G)\). A path is a sequence of distinct vertices where each consecutive pair of vertices is connected by an edge, meaning no vertex or edge is repeated. A path on \(n\) vertices is denoted by \(P_n\). A cycle is a closed path. A cycle on \(n\) vertices is denoted by \(C_n\). A complete graph is a simple graph in which every distinct pair of vertices is connected by an edge. A complete graph on \(n\) vertices is denoted by \(K_n\). The star graph of order \(n\), denoted \(S_n\), is a simple graph with \(n\) vertices in which one vertex is of degree \(n-1\) and the remaining vertices are of degree \(1\).
The Petersen graph \(P\) is an undirected graph with 10 vertices and 15 edges, as shown in Figure 1.
Let \(G = (V,E)\) be a simple graph. A subset \(D\) of \(V\) is said to be a dominating set of \(G\) if each vertex in \(V\) is either in \(D\) or has a neighbour in \(D\). The minimum cardinality of a dominating set of \(G\) is called the domination number of \(G\), \(\gamma(G)\) [6]. A dominating set \(D\) of \(G\) is said to be a total dominating set if every vertex of \(V(G)\) is adjacent to some vertex of \(D\) [5].
A subset \(D\) of \(V\) is said to be an equitable dominating set of \(G\) if for every \(v \in V – D\), there exists a vertex \(u \in D\) such that \(uv \in E(G)\) and \(\lvert \deg(u) – \deg(v) \rvert \leq 1\) [11]. We say that \(u\) equitably dominates \(v\). The minimum cardinality of an equitable dominating set of \(G\), denoted by \(\gamma^{e}(G)\), is called the equitable domination number of \(G\).
Example 1.1. In Figure 2, we have \(\gamma^e(G) = 3\). The set \(\{v_1, v_3, v_4\}\) is a minimum equitable dominating set of \(G\).
A vertex \(u \in V\) is an equitable isolate of \(G\) if \(\lvert d_G(u) – d_G(v) \rvert \ge 2\) for all \(v \in N_G(u)\).
Remark 1.2. An equitable isolate of a graph cannot be dominated equitably by any other vertex of the graph. Hence, every equitable dominating set of a graph contains the equitable isolates of the graph (if they exist).
The concept of equitable domination was introduced by V. Swaminathan and K. M. Dharmalingham [11]. Research on equitable domination has grown steadily, focusing both on exact values for specific graph families and on structural bounds and characterizations. Several papers determine the equitable domination number for classical small families such as paths, cycles, fans, pans, and butterflies [11]. Further studies relating to the equitable domination number of the rooted product of graphs and the corona product of graphs can be seen in [12, 13]. Related works on variations of the parameter, like independent equitable domination and equi-independent equitable domination, offer various directions to researchers [3, 14]. Apart from dominating sets, an equitable dominating set [11] ensures, for each vertex outside it, an equitable neighbour.
In this paper, we study the equitable domination number of certain graph operators such as the double graph, the Mycielskian, and the subdivision of a graph.
The direct product of two graphs \(G\) and \(H\) is the graph \(G \times H\) with \(V(G \times H) = V(G) \times V(H)\) and with adjacency defined by \((v_1, w_1)\) being adjacent to \((v_2, w_2)\) if and only if \(v_1\) is adjacent to \(v_2\) in \(G\) and \(w_1\) is adjacent to \(w_2\) in \(H\). The total graph \(T_n\) on \(n\) vertices is the graph obtained from the complete graph \(K_n\) by adding a loop to every vertex. The double graph \(\mathscr{D}(G)\) of a simple graph \(G\) is defined as the graph \(\mathscr{D}(G) = G \times T_2\) [9]. More precisely, the double graph \(\mathscr{D}(G)\) of a graph \(G\) is constructed by making two copies of \(G\), namely \(G_1\) and \(G_2\), including the initial edge set of each, and adding edges \(u^1v^2\) and \(v^1u^2\) for every edge \(uv\) of \(G\), where \(V(G_i) = \{v^i : v \in V(G)\}, \; i = 1, 2\).
For a graph \(G = (V,E)\), the Mycielskian of \(G\), denoted by \(\mu(G)\), is the graph with vertex set \(V \cup V' \cup \{u\}\), where \(V' = \{x' : x \in V\}\), and edge set \(E \cup \{xy' : xy \in E\} \cup \{y'u : y' \in V'\}\). The vertex \(x'\) is called the twin of the vertex \(x\) (and \(x\) the twin of \(x'\)), and the vertex \(u\) is called the root of \(\mu(G)\) [8].
An edge subdivision is the insertion of a new vertex in the middle of an existing edge. The graph obtained by subdividing each edge of a graph \(G\) exactly once is called the subdivision of \(G\) and is denoted by \(S(G)\).
Remark 2.1. \(\gamma^{e}(S(P_n)) = \gamma^{e}(P_{2n-1}) = \left\lceil \frac{2n – 1}{3} \right\rceil.\)
Remark 2.2. \(\gamma^{e}(S(C_n)) = \gamma^{e}(C_{2n}) = \left\lceil \frac{2n}{3} \right\rceil.\)
Theorem 2.3. Let \(G\) be a graph with \(\Delta(G) \le 3\). Then \[\gamma^{e}(S(G)) \le \min\{\, |V(G)|, |E(G)| \,\}.\]
Proof. Let \(S\) denote the set of all newly introduced vertices in \(G\) as a result of subdividing each edge in \(G\). Then \[V(S(G)) = V(G) \cup S \quad \text{and} \quad |S| = |E(G)|.\] Then \(S\) is a dominating set of \(S(G)\). We have \(d_{S(G)}(u) = 2\) for every \(u \in S\), and \(d_{S(G)}(v) = d_G(v) \le 3\) for all vertices \(v \in V(G)\). Hence, for each vertex \(v \in V(G)\) and \(u \in S\), \[\bigl| d_{S(G)}(v) – d_{S(G)}(u) \bigr| \le 1. \label{eq:6a} \tag{1}\] Thus \(S\) is an equitable dominating set of \(S(G)\). Therefore, \[\gamma^{e}(S(G)) \le |S| = |E(G)|. \label{eq:6b} \tag{2}\]
Clearly, \(V(G)\) is a dominating set of \(S(G)\), and from (1) we get that \(V(G)\) is an equitable dominating set of \(S(G)\). Therefore, \[\gamma^{e}(S(G)) \le |V(G)|. \label{eq:6c} \tag{3}\]
From (2) and (3), we obtain \[\gamma^{e}(S(G)) \le \min\{\, |V(G)|, |E(G)| \,\}.\] ◻
Theorem 2.4. Let \(G\) be a graph with \(\delta(G) \ge 4\). Then there exists no proper equitable dominating set of \(S(G)\).
Proof. Let \(S\) denote the set of all newly introduced vertices in \(G\) as a result of subdividing each edge in \(G\). Then \(V(S(G)) = V(G) \cup S\). Let \(u \in S\) and \(v \in V(G)\). Since \(d_G(v) \ge 4\) for all vertices \(v\) in \(G\), we have \(d_{S(G)}(v) \ge 4\) for all vertices \(v \in V(G)\). Also, \(d_{S(G)}(u) = 2\) for all vertices \(u \in S\). Therefore, \[\lvert d_{S(G)}(v) – d_{S(G)}(u) \rvert \ge 2.\] Thus each vertex of \(S\) is an equitable isolate. Hence every equitable dominating set of \(S(G)\) contains \(S\). Also, vertices of \(G\) are nonadjacent in \(S(G)\). In order to dominate vertices of \(G\), every equitable dominating set of \(S(G)\) must contain \(V(G)\) as well. Then \[\gamma^e(S(G)) \ge \lvert S \rvert + \lvert V(G) \rvert \ge \lvert V(S(G)) \rvert.\] Therefore \(\gamma^e(S(G)) = \lvert V(S(G)) \rvert\), which implies that there exists no proper equitable dominating set of \(S(G)\). ◻
Corollary 2.5. \(\gamma^e(S(K_n)) = n\), for \(n \ge 5\).
Theorem 2.6. Let \(G\) be a graph with at least two vertices. Then \(\gamma^e(S(G)) = 1\) if and only if \(G = P_2\).
Proof. Suppose that \(\gamma^e(S(G)) = 1\). Let \(S\) denote the set of all newly introduced vertices in \(G\) as a result of subdividing each edge in \(G\). Then \(V(S(G)) = V(G) \cup S\). Let \(\{v\}\) be a \(\gamma^e\)-set of \(S(G)\). Then either \(v \in S\) or \(v \in V(G)\).
Case 1. \(v \in S\).
Let \(v\) be the vertex obtained as a result of subdividing the edge \(u_1u_2\) of \(G\). Suppose that there exists a vertex \(u_3\) in \(G\) in addition to the vertices \(u_1, u_2\). Since \(\{v\}\) is a \(\gamma^e\)-set of \(S(G)\), \(u_3\) must be adjacent to \(v\) in \(S(G)\). This implies that \(d_{S(G)}(v) \ge 3\), which is a contradiction to the fact that a vertex of \(S(G)\) obtained by subdividing edges of \(G\) has degree 2. Hence \(V(G) = \{u_1, u_2\}\), which implies that \(G = P_2\).
Case 2. \(v \in V(G)\).
Suppose that there exists a vertex \(u\) in \(G\) in addition to the vertex \(v\). Then \(v\) is not adjacent to \(u\) in \(S(G)\). Thus \(v\) cannot dominate \(u\) in \(S(G)\), which is a contradiction to the assumption that \(\{v\}\) is a \(\gamma^e\)-set of \(S(G)\). Therefore, this case does not occur.
Conversely, suppose that \(G = P_2\). Then \(S(G) = P_3\). As \(\gamma^e(P_n) = \left\lceil \frac{n}{3} \right\rceil\) [11], we get that \(\gamma^e(S(G)) = 1\). ◻
Theorem 2.7. For any graph \(G\) with at least three vertices, \(\gamma^{e}(S(G)) = 2\) if and only if either \(G = P_3\) or \(G = C_3\).
Proof. Let \(S\) denote the set of all newly introduced vertices in \(G\) as a result of subdividing each edge in \(G\). Then \(V(S(G)) = V(G) \cup S\). Suppose \(\gamma^{e}(S(G)) = 2\). Let \(D = \{v_1, v_2\}\) be a \(\gamma^{e}\)-set of \(S(G)\).
Case 1. \(D \subseteq S\).
Then \(D = S\), because if there exists a vertex in \(S\) that is not in \(D\), it cannot be dominated by \(D\), as there is no adjacency between vertices of \(S\) in \(S(G)\). Thus there are exactly two newly introduced vertices as a result of subdivision, which implies that \(G\) has exactly two edges. Hence \(G = P_3\).
Case 2. \(D \subseteq V(G)\).
Then \(D = V(G)\), because if there exists a vertex in \(V(G)\) that is not in \(D\), it cannot be dominated by \(D\), as there is no adjacency between vertices of \(V(G)\) in \(S(G)\). This is a contradiction. Therefore \(D = V(G)\), which implies that \(G\) has exactly two vertices, contradicting the assumption that \(G\) has at least three vertices. Hence this case does not occur.
Case 3. \(v_1 \in V(G)\) and \(v_2 \in S\).
Claim. \(v_1\) and \(v_2\) are not adjacent in \(S(G)\).
Suppose, for a contradiction, that \(v_1\) and \(v_2\) are adjacent in \(S(G)\). Then there exists a vertex \(u\) in \(G\) adjacent to \(v_1\), and \(v_2\) is the vertex obtained by subdividing the edge \(uv_1\). Then \(V(G) = \{u, v_1\}\), for if there exists a vertex \(v\) in \(G\) in addition to \(u\) and \(v_1\), then \(v\) cannot be dominated by \(D\) in \(S(G)\). This is a contradiction. Thus \(V(G) = \{u, v_1\}\), which implies that \(G\) has exactly two vertices, again contradicting the assumption that \(G\) has at least three vertices. Therefore \(v_1\) and \(v_2\) are not adjacent in \(S(G)\), establishing the claim.
Suppose that \(v_2\) is the vertex obtained as a result of subdividing the edge \(u_1u_2\) of \(G\). Then \(V(G) = \{v_1, u_1, u_2\}\), because if there exists a vertex \(u_3\) in \(G\) in addition to the vertices \(v_1, u_1, u_2\), then, since \(D\) is a \(\gamma^{e}\)-set of \(S(G)\), \(u_3\) must be adjacent to \(v_2\) in \(S(G)\). This would imply that \(d_{S(G)}(v_2) \ge 3\), which is a contradiction to the fact that a vertex of \(S(G)\) obtained by subdividing edges of \(G\) has degree 2. Hence \(G\) has exactly three vertices. Therefore either \(G = P_3\) or \(G = C_3\). ◻
Theorem 3.1. For any graph \(G\), \(\gamma^{e}(\mathscr{D}(G)) \ge \gamma^{e}(G)\).
Proof. Let \(G_1\) and \(G_2\) denote the two copies of \(G\) in \(\mathscr{D}(G)\). Then \[V(\mathscr{D}(G)) = V(G_1) \cup V(G_2),\] and \(V(G_i) = \{v^{i} : v \in V(G)\}\) for \(i = 1,2\). Suppose, for a contradiction, that \[\gamma^{e}(\mathscr{D}(G)) < \gamma^{e}(G).\] Let \(D\) be a \(\gamma^{e}\)-set of \(\mathscr{D}(G)\). Then \(D \subseteq \{v^{i} : v \in V(G),\, i = 1,2\}\). Define \[D' = \{\, v \in V(G) : v^{i} \in D \text{ for some } i \in \{1,2\} \,\}.\] Then \[\label{eq:6d} \lvert D' \rvert \le \lvert D \rvert = \gamma^{e}(\mathscr{D}(G)). \tag{4}\]
Let \(u \in V(G) \setminus D'\). Then \(u^{1}\) and \(u^{2}\) do not belong to \(D\). Since \(D\) is a \(\gamma^{e}\)-set of \(\mathscr{D}(G)\), there exists a vertex \(v^{i} \in D\) such that \(u^{1}\) is adjacent to \(v^{i}\) in \(\mathscr{D}(G)\) and \[\lvert d_{\mathscr{D}(G)}(u^{1}) – d_{\mathscr{D}(G)}(v^{i}) \rvert \le 1.\] Since \[d_{\mathscr{D}(G)}(u^{1}) = 2 d_{G}(u) \quad \text{and} \quad d_{\mathscr{D}(G)}(v^{i}) = 2 d_{G}(v),\] we obtain \[\lvert 2 d_{G}(u) – 2 d_{G}(v) \rvert \le 1,\] which implies \[\lvert d_{G}(u) – d_{G}(v) \rvert \le 1.\] Thus \(D'\) is an equitable dominating set of \(G\). But by (4), \[\lvert D' \rvert \le \lvert D \rvert = \gamma^{e}(\mathscr{D}(G)) < \gamma^{e}(G),\] which is a contradiction, since \(\gamma^{e}(G)\) is the minimum cardinality of an equitable dominating set of \(G\). ◻
Theorem 3.2. Let \(G\) be a regular graph. If there exists a \(\gamma^{e}\)-set of \(G\) which is also a total dominating set, then \(\gamma^{e}(\mathscr{D}(G)) = \gamma^{e}(G)\).
Proof. Let \(G_1\) and \(G_2\) denote the two copies of \(G\) in \(\mathscr{D}(G)\). Then \[V(\mathscr{D}(G)) = V(G_1) \cup V(G_2), \quad V(G_i) = \{v^{i} : v \in V(G)\}, \; i = 1,2.\] Let \(D\) be a \(\gamma^{e}\)-set of \(G\) which is a total dominating set. Define \[D' = \{v^{1} : v \in D\}.\] Then \(\lvert D' \rvert = \lvert D \rvert\).
Claim 1. \(D'\) is an equitable dominating set of \(\mathscr{D}(G)\).
Let \(v_k^{\,i} \in V(\mathscr{D}(G)) \setminus D'\). Then \(v_k \in V(G) \setminus D\). Since \(D\) is a \(\gamma^{e}\)-set of \(G\), there exists a vertex \(v_s \in D\) such that \(v_k\) is adjacent to \(v_s\) in \(G\). Hence \(v_k^{\,i}\) is adjacent to \(v_s^{\,1}\) in \(\mathscr{D}(G)\), and since \(d_{\mathscr{D}(G)}(x^{j}) = 2 d_G(x)\) for all \(x \in V(G)\), we have \[\lvert d_{\mathscr{D}(G)}(v_k^{\,i}) – d_{\mathscr{D}(G)}(v_s^{\,1}) \rvert = \lvert 2 d_G(v_k) – 2 d_G(v_s) \rvert = 2 \lvert d_G(v_k) – d_G(v_s) \rvert = 0 \le 1,\] because \(G\) is regular.
The vertices of \(\mathscr{D}(G)\) that remain to be dominated are those of the form \(v^{2}\) with \(v \in D\). Let \(v^{2}\) be such a vertex. Since \(D\) is a total dominating set of \(G\), there exists \(v_t \in D\) such that \(v\) is adjacent to \(v_t\) in \(G\). As \(v_t \in D\), we have \(v_t^{\,1} \in D'\), and \(v^{2}\) is adjacent to \(v_t^{\,1}\) in \(\mathscr{D}(G)\). Since \(G\) is regular, \(\mathscr{D}(G)\) is also regular, and \[\lvert d_{\mathscr{D}(G)}(v^{2}) – d_{\mathscr{D}(G)}(v_t^{\,1}) \rvert = 0 \le 1.\] Therefore \(D'\) is an equitable dominating set of \(\mathscr{D}(G)\), which gives \[\gamma^{e}(\mathscr{D}(G)) \le \lvert D' \rvert = \gamma^{e}(G).\] By Theorem 3.1, \(\gamma^{e}(\mathscr{D}(G)) \ge \gamma^{e}(G)\). Hence, \[\gamma^{e}(\mathscr{D}(G)) = \gamma^{e}(G).\] ◻
Theorem 3.3. Let \(G\) be a graph with at least two vertices. Then \(\gamma^{e}(\mathscr{D}(G)) = 2\) if and only if one of the following conditions holds: (a) \(G = K_n\) for some \(n\); (b) \(G\) is a regular graph and there exists a \(\gamma^{e}\)-set of \(G\) of cardinality \(2\) whose vertices are adjacent.
Proof. Suppose that \(\gamma^{e}(\mathscr{D}(G)) = 2\). Let \(G_1, G_2\) denote the two copies of \(G\) in \(\mathscr{D}(G)\). Then \[V(\mathscr{D}(G)) = V(G_1) \cup V(G_2), \qquad V(G_i) = \{v^{i} : v \in V(G)\}, \; i = 1,2.\] Let \(D\) be a \(\gamma^{e}\)-set of \(\mathscr{D}(G)\).
Case 1. \(D \subseteq V(G_1)\).
Let \(D = \{v_k^{1}, v_\ell^{1}\}\). If \(V(G) = \{v_k, v_\ell\}\), then \(G = K_2\). Hence assume that \(G\) has at least three vertices. Since \(D\) is a \(\gamma^{e}\)-set of \(\mathscr{D}(G)\), the set \(\{v_k, v_\ell\}\) is a dominating set of \(G\). In \(\mathscr{D}(G)\), \(v_k^{1}\) is not adjacent to \(v_k^{2}\). Since \(D\) is a \(\gamma^{e}\)-set of \(\mathscr{D}(G)\), the vertex \(v_k^{2}\) is dominated by \(v_\ell^{1}\) and \[\lvert d_{\mathscr{D}(G)}(v_k^{2}) – d_{\mathscr{D}(G)}(v_\ell^{1}) \rvert \le 1.\] Thus, \[\lvert 2 d_G(v_k) – 2 d_G(v_\ell) \rvert \le 1,\] which implies \[d_G(v_k) = d_G(v_\ell).\] Let \[d_G(v_k) = d_G(v_\ell) = t. \label{eq:6e} \tag{5}\]
Claim 1. \(d_G(v) = t\) for every \(v \in V(G)\).
Let \(v\) be a vertex in \(G\) different from \(v_k\) and \(v_\ell\). Then in \(\mathscr{D}(G)\), \(v^{1}\) is equitably dominated by either \(v_k^{1}\) or \(v_\ell^{1}\). Suppose \(v_k^{1}\) equitably dominates \(v^{1}\). Then \(v_k\) is adjacent to \(v\) in \(G\) and \[\lvert d_{\mathscr{D}(G)}(v_k^{1}) – d_{\mathscr{D}(G)}(v^{1}) \rvert \le 1,\] so \[\lvert 2 d_G(v_k) – 2 d_G(v) \rvert \le 1,\] which implies \[d_G(v) = d_G(v_k).\] Since \(v\) was arbitrary, \(d_G(v) = d_G(v_k)\) for all \(v \in V(G)\). Thus \(G\) is a regular graph and, from (5), \(d_G(v) = t\) for every \(v \in V(G)\).
If \(t = \lvert V(G) \rvert – 1\), then \(G = K_n\), where \(n = \lvert V(G) \rvert\). Suppose \(t \neq \lvert V(G) \rvert – 1\). Then \(G\) does not contain any universal vertex. Hence \(\gamma^{e}(G) \ge 2\). From Theorem 3.1, \(\gamma^{e}(\mathscr{D}(G)) \ge \gamma^{e}(G)\), so \(2 \ge \gamma^{e}(G)\), and thus \(\gamma^{e}(G) = 2\). As \(G\) is regular, every dominating set of \(G\) is an equitable dominating set of \(G\). Hence \(\{v_k, v_\ell\}\) is an equitable dominating set of \(G\) with \(v_k\) adjacent to \(v_\ell\). Since \(\gamma^{e}(G) = 2\), \(\{v_k, v_\ell\}\) is a \(\gamma^{e}\)-set of \(G\).
Case 2. \(D \subseteq V(G_2)\).
Argue as in Case 1, replacing \(G_1\) with \(G_2\) and vertices of the form \(v^{1}\) with \(v^{2}\).
Case 3. \(D \cap V(G_1) \neq \varnothing\) and \(D \cap V(G_2) \neq \varnothing\).
Let \(D = \{v_k^{1}, v_s^{2}\}\). First, suppose \(k = s\). Since \(D\) is a \(\gamma^{e}\)-set of \(\mathscr{D}(G)\), \(v_k\) is a universal vertex of \(G\). Hence \(d_G(v_k) = \lvert V(G) \rvert – 1\). Let \(u \in V(G)\) with \(u \neq v_k\). Then \(u^{1} \in V(\mathscr{D}(G))\) and \(u^{1}\) is equitably dominated by either \(v_k^{1}\) or \(v_k^{2}\). Suppose \(v_k^{1}\) equitably dominates \(u^{1}\). Then \[\lvert d_{\mathscr{D}(G)}(v_k^{1}) – d_{\mathscr{D}(G)}(u^{1}) \rvert \le 1,\] which gives \[\lvert 2 d_G(v_k) – 2 d_G(u) \rvert \le 1,\] and hence \[d_G(u) = d_G(v_k) = \lvert V(G) \rvert – 1.\] Since \(u\) was chosen arbitrarily, \(d_G(u) = \lvert V(G) \rvert – 1\) for every \(u \in V(G)\). Thus \(G = K_n\), where \(n = \lvert V(G) \rvert\).
Now suppose \(k \neq s\). If \(V(G) = \{v_k, v_s\}\), then \(G = K_2\). Hence assume \(G\) has at least three vertices. The vertex \(v_k^{2}\) in \(\mathscr{D}(G)\) is equitably dominated by \(v_s^{2}\) in the \(\gamma^{e}\)-set \(D\). This implies that \(v_k\) and \(v_s\) are adjacent in \(G\). Also, \[\lvert d_{\mathscr{D}(G)}(v_k^{2}) – d_{\mathscr{D}(G)}(v_s^{2}) \rvert \le 1 \quad \Longrightarrow \quad \lvert 2 d_G(v_k) – 2 d_G(v_s) \rvert \le 1,\] so \[d_G(v_k) = d_G(v_s).\]
Let \(w\) be a vertex in \(G\) different from \(v_k\) and \(v_s\). Then \(w^{1} \in V(\mathscr{D}(G))\) and \(w^{1}\) is equitably dominated by either \(v_k^{1}\) or \(v_s^{2}\) in \(D\). Suppose \(w^{1}\) is equitably dominated by \(v_k^{1}\). Then \[\lvert d_{\mathscr{D}(G)}(v_k^{1}) – d_{\mathscr{D}(G)}(w^{1}) \rvert \le 1,\] so \[\lvert 2 d_G(v_k) – 2 d_G(w) \rvert \le 1,\] and hence \[d_G(w) = d_G(v_k).\] Since \(w\) was chosen arbitrarily, \(G\) is \(r\)-regular for some \(r\). If \(r = \lvert V(G) \rvert – 1\), then \(G = K_{r+1}\). If not, \(G\) does not contain any universal vertex. Hence \(\gamma^{e}(G) \ge 2\). From Theorem 3.1, \(\gamma^{e}(\mathscr{D}(G)) \ge \gamma^{e}(G)\), so \(2 \ge \gamma^{e}(G)\), and thus \(\gamma^{e}(G) = 2\). As \(G\) is regular, every dominating set is an equitable dominating set. Hence \(\{v_k, v_s\}\) is an equitable dominating set of \(G\) with \(v_k\) adjacent to \(v_s\). Since \(\gamma^{e}(G) = 2\), \(\{v_k, v_s\}\) is a \(\gamma^{e}\)-set of \(G\).
Conversely, suppose that \(G = K_n\) for some \(n\). Let \(v \in V(G)\). Then \(\{v\}\) is a \(\gamma^{e}\)-set of \(K_n\). Correspondingly, \(\{v^{1}, v^{2}\}\) is a \(\gamma^{e}\)-set of \(\mathscr{D}(G)\). Hence \(\gamma^{e}(\mathscr{D}(G)) = 2\).
Now suppose that \(G\) is a regular graph and there exists a \(\gamma^{e}\)-set of \(G\) of cardinality \(2\) with adjacent vertices. Then, by Theorem 3.2, \(\gamma^{e}(\mathscr{D}(G)) = \gamma^{e}(G) = 2\). ◻
Remark 4.1. \(\gamma^{e}(\mu(G)) \ge 2\), since \(\gamma(\mu(G)) \ge 2\).
Theorem 4.2. For any graph \(G\) with \(n \ge 2\) vertices, \(\gamma^{e}(\mu(G)) = 2\) if and only if \(G = K_n\).
Proof. Let \(V(G) = \{v_1, v_2, \ldots, v_n\}\). Let \(u_i\) denote the twin vertex of \(v_i\) in \(\mu(G)\), and let \(w\) denote the apex vertex of \(\mu(G)\). Let \[U(G) = \{u_i : v_i \in V(G)\}.\] Then \[V(\mu(G)) = V(G) \cup U(G) \cup \{w\}.\] Suppose that \(\gamma^{e}(\mu(G)) = 2\). Let \(D\) be a \(\gamma^{e}\)-set of \(\mu(G)\). Then \(D \not\subseteq V(G)\), because if \(D \subseteq V(G)\), then the vertex \(w\) in \(\mu(G)\) cannot be dominated by \(D\), as there is no adjacency between \(w\) and vertices of \(V(G)\). Thus \(D\) must be of one of the following forms:
\(D = \{u_k, w\}\) for some \(k\);
\(D = \{u_k, v_s\}\) for some \(k\) and \(s\);
\(D = \{v_k, w\}\) for some \(k\).
Case 1. \(D = \{u_k, w\}\) for some \(k\).
In this case the vertex \(v_k\) is not dominated by \(D\), as \(v_k\) is not adjacent to \(u_k\) nor to \(w\). This contradicts the assumption that \(D\) is a \(\gamma^{e}\)-set of \(\mu(G)\). Hence this case does not occur.
Case 2. \(D = \{u_k, v_s\}\) for some \(k\) and \(s\).
Here we must have \(s = k\), otherwise \(u_s\), the twin of \(v_s\), cannot be dominated by \(D\). Thus \(D = \{u_k, v_k\}\). The vertex \(w\) is equitably dominated by \(u_k\) in \(D\), hence \[\lvert d_{\mu(G)}(u_k) – d_{\mu(G)}(w) \rvert \le 1. \label{eq:ff} \tag{6}\] Since \(d_{\mu(G)}(w) = \lvert V(G) \rvert\), from (6) we get either \[d_{\mu(G)}(u_k) = \lvert V(G) \rvert \quad \text{or} \quad d_{\mu(G)}(u_k) = \lvert V(G) \rvert – 1.\]
Suppose first that \(d_{\mu(G)}(u_k) = \lvert V(G) \rvert\). Then \(d_G(v_k) = \lvert V(G) \rvert – 1\), so \(v_k\) is a universal vertex of \(G\). Let \(v_t \in V(G)\) with \(v_t \ne v_k\). Since \(v_k\) is universal in \(G\), \(v_k\) is adjacent to \(v_t\), hence \(u_k\) is adjacent to \(v_t\) in \(\mu(G)\). As \(d_{\mu(G)}(u_k) = \lvert V(G) \rvert\) and \(d_{\mu(G)}(v_t) \le 2(\lvert V(G) \rvert – 1)\), we have \[\lvert d_{\mu(G)}(u_k) – d_{\mu(G)}(v_t) \rvert \ge 1.\] Hence \(u_k\) cannot equitably dominate \(v_t\). Thus \(v_k \in D\) must equitably dominate \(v_t\), so \[\lvert d_{\mu(G)}(v_t) – d_{\mu(G)}(v_k) \rvert \le 1,\] which gives \[\lvert 2 d_G(v_t) – 2 d_G(v_k) \rvert \le 1.\] Thus \[d_G(v_t) = d_G(v_k) = \lvert V(G) \rvert – 1.\] Since \(v_t\) was arbitrary, we get \(d_G(v) = \lvert V(G) \rvert – 1\) for all \(v \in V(G)\). Hence \(G\) is a regular graph of degree \(\lvert V(G) \rvert – 1\), so \(G = K_n\), where \(n = \lvert V(G) \rvert\).
Now suppose that \(d_{\mu(G)}(u_k) = \lvert V(G) \rvert – 1\). Then \(d_G(v_k) = \lvert V(G) \rvert – 2\). This implies that there exists a vertex \(v_p \in V(G)\) which is not adjacent to \(v_k\). Hence in \(\mu(G)\), \(u_k\) is not adjacent to \(v_p\), so \(v_p\) is not dominated by either vertex in \(D\). This contradicts the assumption that \(D\) is a \(\gamma^{e}\)-set of \(\mu(G)\). Therefore this case does not occur.
Case 3. \(D = \{v_k, w\}\) for some \(k\).
Let \(v_t \in V(G)\) with \(v_t \ne v_k\). Since \(D\) is a \(\gamma^{e}\)-set of \(\mu(G)\) and \(w\) is not adjacent to \(v_t\) in \(\mu(G)\), the vertex \(v_t\) is equitably dominated by \(v_k \in D\). Hence \[\lvert d_{\mu(G)}(v_k) – d_{\mu(G)}(v_t) \rvert \le 1,\] which gives \[\lvert 2 d_G(v_t) – 2 d_G(v_k) \rvert \le 1,\] and therefore \[d_G(v_t) = d_G(v_k). \label{eq:6g} \tag{7}\] Since \(v_t\) was arbitrary, \(G\) is a regular graph with degree \(d_G(v_k)\). Moreover, in \(\mu(G)\) the vertex \(v_k \in D\) equitably dominates all vertices of \(V(G)\), since there is no adjacency between \(w\) and vertices of \(V(G)\). Hence \(v_k\) must be adjacent in \(G\) to all other vertices of \(G\), so \[d_G(v_k) = \lvert V(G) \rvert – 1.\] From (7) we conclude that \(G\) is a regular graph of degree \(\lvert V(G) \rvert – 1\), so \(G = K_n\), where \(n = \lvert V(G) \rvert\).
Conversely, suppose that \(G = K_n\) for some \(n\). Let \(v_p\) be any vertex of \(G\), and let \(T = \{v_p, w\}\).
Claim. \(T\) is an equitable dominating set of \(\mu(G)\).
Clearly \(T\) is a dominating set of \(\mu(G)\). Since \(d_G(v_p) = n – 1\), we have \(d_{\mu(G)}(v_p) = 2(n – 1)\). Let \(v_q \in V(G)\). Then \(v_q\) is adjacent to \(v_p\) in \(G\), hence \(v_q\) is adjacent to \(v_p\) in \(\mu(G)\), and \[\lvert d_{\mu(G)}(v_q) – d_{\mu(G)}(v_p) \rvert = \lvert 2(n – 1) – 2(n – 1) \rvert \le 1.\] Hence in \(\mu(G)\), \(v_p\) equitably dominates all vertices of \(V(G)\). The vertices of \(\mu(G)\) that remain to be equitably dominated are those in \(U(G)\). Let \(u_k \in U(G)\). Then \(u_k\) is adjacent to \(w\) in \(\mu(G)\), and \[\lvert d_{\mu(G)}(w) – d_{\mu(G)}(u_k) \rvert = \lvert n – n \rvert \le 1.\] Thus \(T\) is an equitable dominating set of \(\mu(G)\), so \(\gamma^{e}(\mu(G)) \le 2\). Together with Remark 4.1, this gives \(\gamma^{e}(\mu(G)) = 2\). ◻
Theorem 4.3. Let \(G\) be a graph with \(n\) vertices, where \(n \ge 6\). Suppose that for every vertex \(v\) in \(G\) we have \(d_G(v) \in \{n-1, n-2\}\) and no two adjacent vertices have the same degree. Then \(\gamma^{e}(\mu(G)) = n + 1\).
Proof. Let \(V(G) = \{v_1, v_2, \ldots, v_n\}\). Let \(u_i\) denote the twin vertex of \(v_i\) in \(\mu(G)\) and let \(U(G) = \{u_i : v_i \in V(G)\}\). Let \(w\) denote the apex vertex of \(\mu(G)\). Then \[V(\mu(G)) = V(G) \cup U(G) \cup \{w\}.\] Let \(D = \{w\} \cup V(G)\).
Claim 1. \(D\) is an equitable dominating set of \(\mu(G)\).
Since \(d_G(v) \in \{n-1, n-2\}\) for all \(v \in V(G)\), it follows that \(d_{\mu(G)}(u) \in \{n, n-1\}\) for all \(u \in U(G)\). Also \(d_{\mu(G)}(w) = n\), and in \(\mu(G)\) the vertex \(w\) is adjacent to all vertices of \(U(G)\). Therefore, for each vertex \(u \in U(G)\), \[\lvert d_{\mu(G)}(w) – d_{\mu(G)}(u) \rvert \le 1.\] Thus \(w\) equitably dominates all vertices of \(U(G)\), and hence \(D\) is an equitable dominating set of \(\mu(G)\). Therefore, \[\gamma^{e}(\mu(G)) \le \lvert D \rvert = n + 1. \label{eq:6h} \tag{8}\]
Since \(d_G(v) \in \{n-1, n-2\}\) for all \(v \in V(G)\), we have \(d_{\mu(G)}(v) \in \{2(n-1), 2(n-2)\}\) for all \(v \in V(G)\), and \(d_{\mu(G)}(u) \in \{n, n-1\}\) for all \(u \in U(G)\). Because no two adjacent vertices of \(G\) have the same degree and \(n \ge 6\), it follows that in \(\mu(G)\) the absolute difference of the degrees of any two vertices of \(V(G)\) is at least \(2\). Similarly, in \(\mu(G)\) the absolute difference of the degrees of any two vertices, one from \(V(G)\) and the other from \(U(G)\), is at least \(2\). Hence every equitable dominating set of \(\mu(G)\) must contain \(V(G)\).
Also, \(w\) cannot be dominated by the vertices of \(V(G)\), as there is no adjacency between \(w\) and \(V(G)\). Therefore, in order to dominate the apex vertex \(w\), every equitable dominating set of \(\mu(G)\) must contain at least one vertex from \(\{w\} \cup U(G)\). Thus \[\gamma^{e}(\mu(G)) \ge \lvert V(G) \rvert + 1 = n + 1. \label{eq:6i} \tag{9}\]
From (8) and (9) we obtain \(\gamma^{e}(\mu(G)) = n + 1\). ◻
Theorem 4.4. Let \(G\) be a \(k\) regular graph with at least 4 vertices. Then \(\gamma^e(\mu( G)) \leq \gamma^e(G) + \arrowvert V(G) \arrowvert + 1\) and the equality holds if and only if \(3\leq k \leq n – 3\).
Proof. Let \(V(G) = \{ v_1, v_2,…, v_n \}\). Let \(u_i\) denote the twin vertex of \(v_i\) in \(\mu( G)\) and let \(U(G) = \{u_i : v_i \in V(G) \}\). Let \(w\) denote the apex vertex of \(\mu( G)\). Then \(V(\mu( G)) = V(G) \cup U(G) \cup \{w\}\). Let \(D\) be a \(\gamma^e\) – set of \(G\). Let \(D' = D \cup U(G) \cup \{w\}\). Then \(D'\) is a dominating set of \(\mu( G)\) and as \(G\) is a regular graph, \(D'\) is an equitable dominating set of \(\mu( G)\). Hence \[\gamma^e(\mu( G)) \leq \arrowvert D' \arrowvert = \gamma^e(G) + \arrowvert V(G) \arrowvert + 1. \label{eq:6j} \tag{10}\]
Suppose that the equality holds.
\[\gamma^e(\mu( G)) = \gamma^e(G) + \arrowvert V(G) \arrowvert + 1.\]
As \(G\) is a \(k\) regular graph, we have \[\begin{aligned} d_{\mu( G)}(v) =& 2k,\, for\: every \:v \in V(G),\\ d_{\mu( G)}(u) =& k + 1, \, for\: every \: u \in U(G) ,\\ d_{\mu( G)}(w) =& n . \end{aligned}\]
If possible suppose that \(k > n – 3\). Then either \(k = n – 2\) or \(k = n – 1\). Let \(v_m \in V(G)\). Then either \(d_G(v_m) = n – 2\) or \(d_G(v_m) = n – 1\). Then in \(\mu( G)\), either \(d_{\mu( G)}(u_m) = n – 1\) or \(d_{\mu( G)}(u_m) = n\), where \(u_m\) is the twin vertex of \(v_m\). Let \(T = D \cup U(G)\). As \(D\) is a \(\gamma^e\) – set of \(G\), and \(G\) is a \(k\) regular graph, the vertices of \(D\) equitably dominates the vertices of \(V(G)\) in \(\mu( G)\). Any vertex in \(U(G)\) can equitably dominate the apex vertex \(w\) of \(\mu( G)\). Thus \(T\) is an equitable dominating set of \(\mu( G)\). Hence \(\gamma^e(\mu( G)) \leq \arrowvert T \arrowvert = \gamma^e(G) + \arrowvert V(G) \arrowvert\) which is a contradiction to the assumption that \(\gamma^e(\mu( G)) = \gamma^e(G) + \arrowvert V(G) \arrowvert + 1\). Thus \(k \leq n – 3\).
If possible assume that \(k \leq 2\). Let \(D''\) denote the set of all twin vertices of the vertices in \(D\). Let \(T' = D \cup D'' \cup \{w\}\).
Claim 1. \(T'\) is an equitable dominating set of \(\mu( G)\).
Let \(x \in V(\mu( G)) – T'\). Then either \(x \in V(G)\) or \(x \in U(G)\). Suppose that \(x \in V(G)\). Then \(x = v_s\) for some \(s\). As \(D\) is a \(\gamma^e\) – set of \(G\), there exists a vertex \(v_t\) in \(D\) such that \(v_s\) and \(v_t\) are adjacent in \(G\) and \(\arrowvert d_G(v_s) – d_G(v_t) \arrowvert = 0 \leq 1\). Therefore \(v_t \in T'\), \(v_s\) and \(v_t\) are adjacent in \(\mu( G)\) and \[\arrowvert d_{\mu(G)}(v_s) – d_{\mu(G)}(v_t) \arrowvert = 2[\arrowvert d_G(v_s) – d_G(v_t) \arrowvert] = 0.\]
Let \(x \in U(G)\). Then \(x = u_p\) for some \(p\). Its twin vertex \(v_p \in V(G)\) and \(v_p \notin D\). Then as \(D\) is a \(\gamma^e\) – set of \(G\), there exists a vertex \(v_q\) in \(D\) such that \(v_p\) and \(v_q\) are adjacent in \(G\) and \(\arrowvert d_G(v_p) – d_G(v_q) \arrowvert = 0 \leq 1\). Hence \(v_q \in T'\). \(u_p\) and \(v_q\) are adjacent in \(\mu( G)\). As \(k \leq 2\),
\[\arrowvert d_{\mu(G)}(u_p) – d_{\mu(G)}(v_q) \arrowvert = \arrowvert d_G(v_p) + 1 – 2d_G(v_q) \arrowvert = \arrowvert k + 1 – 2k \arrowvert = \arrowvert 1 – k\arrowvert \leq 1 .\]
Thus \(T'\) is an equitable dominating set of \(\mu( G)\) which gives \(\gamma^e(\mu( G)) \leq \arrowvert T' \arrowvert = 2\gamma^e(G) + 1\). As \(G\) is a regular graph \(\gamma^e(G) = \gamma(G) < \arrowvert V(G) \arrowvert\) giving \(\gamma^e(\mu( G)) = 2\gamma^e(G) + 1 < \gamma^e(G) + \arrowvert V(G) \arrowvert + 1\) which is a contradiction to the assumption that \(\gamma^e(\mu( G)) = \gamma^e(G) + \arrowvert V(G) \arrowvert + 1\). Thus \(k \geq 3\).
Conversely, suppose that \(3\leq k \leq n – 3\). Then the apex vertex \(w\) is an equitable isolate in \(\mu( G)\) because for any vertex \(u \in U(G)\), \(d_{\mu(G)}(u) \leq n – 2\), \(d_{\mu(G)}(w) = n\) and hence \(\arrowvert d_{\mu(G)}(w) – d_{\mu(G)}(u) \arrowvert \geq 2\). Also all the vertices of \(U(G)\) are equitable isolates in \(\mu( G)\) because for any vertex \(u \in U(G)\) and \(v \in V(G)\), \[\arrowvert d_{\mu(G)}(u) – d_{\mu(G)}(v) \arrowvert = \arrowvert k + 1 – 2k \arrowvert= \arrowvert 1 – k\arrowvert \geq 2, \; as \; k \geq 3.\]
Thus every equitable dominating set of \(\mu( G)\) must contain \(U(G) \cup \{w\}\). As the vertices in \(U(G) \cup \{w\}\) does not equitably dominate the vertices of \(V(G)\), inorder to equitably dominate the vertices of \(V(G)\), every equitable dominating set of \(\mu( G)\) must contain at least \(\gamma^e(G)\) vertices. Thus \[\gamma^e(\mu( G)) \geq \gamma^e(G) + \arrowvert V(G) \arrowvert + 1. \label{eq:6k} \tag{11}\]
Eqs. (10) and (11) gives \[\gamma^e(\mu( G)) = \gamma^e(G) + \arrowvert V(G) \arrowvert + 1.\] ◻
Corollary 4.5. For the Petersen Graph \(P\), \(\gamma^e(\mu( P)) = 14\).
Proof. As the Petersen Graph \(P\) is regular, \(\gamma^e(P) = \gamma(P) = 3\). Therefore from Theorem 4.4, \(\gamma^e(\mu( P)) = 3 + 10 + 1 = 14\). ◻
This work focuses on the equitable domination number of key graph operators, including the double graph, Mycielskian and subdivision graphs. We establish bounds and provide characterizations for cases where the equitable domination number is 1 as well as 2 in the context of these operators. In addition, we address cases concerning regular graphs in our results. This work opens a deeper dive into the equitable domination number of more graph operators like line graph, edge contraction etc. The study can be extended to finding the equitable domination number of the graph operators like double, subdivision and mycielskian upon their action on product graphs.