Nordhaus–Gaddum-Type Results on the Connected Edge Domination Number

A connected edge dominating set of a connected graph \(G=(V,E)\) $G=(V,E)$ is a subset X of E such that the edge-induced subgraph G[X] is connected and each \(e\in E(G){\setminus } X\) $e\in E(G)\backslash X$ has at least one neighbor in X. The connected edge domination number \(\gamma '_{c}(G)\) ${\gamma }_c^{\prime }(G)$ of G is the minimum cardinality of a connected edge dominating set of G. An edge dominating set X of a graph G is called a 2-edge-connected edge dominating set if G[X] is 2-edge-connected. The 2-edge-connected edge dominating number \(\gamma '_{2ec}(G)\) ${\gamma }_{2ec}^{\prime }(G)$ is the minimum size of a 2-edge-connected edge dominating set of G. In this paper, we obtain the sharp lower bounds for \(\gamma '_{c}(G)+\gamma '_{c}(\overline{G})\) ${\gamma }_c^{\prime }(G)+{\gamma }_c^{\prime }(\overline{G})$ and \(\gamma '_{c}(G)\cdot \gamma '_{c}(\overline{G})\) ${\gamma }_c^{\prime }(G)·{\gamma }_c^{\prime }(\overline{G})$ . Moreover, we characterize the classes of graphs attaining the lower bounds and study the relationship between \(\gamma '_{c}(G)\) ${\gamma }_c^{\prime }(G)$ and several other parameters, such as independent number and vertex cover number. In addition, we show that \(3\le \gamma '_{2ec}(G)\le \lfloor \frac{3}{2}(n-1) \rfloor \) $3\le {\gamma }_{2ec}^{\prime }(G)\le \lfloor \frac{3}{2}(n-1)\rfloor$ if G is 2-edge-connected. We also obtain the upper and lower bounds for \(\gamma '_{2ec}(G)+\gamma '_{2ec}(\overline{G})\) ${\gamma }_{2ec}^{\prime }(G)+{\gamma }_{2ec}^{\prime }(\overline{G})$ and \(\gamma '_{2ec}(G)\cdot \gamma '_{2ec}(\overline{G})\) ${\gamma }_{2ec}^{\prime }(G)·{\gamma }_{2ec}^{\prime }(\overline{G})$ and characterize the classes of graphs attaining the lower bounds.