Let \(G(V,E)\) be a graph. A subset \(S\) of \(V\) is called a dominating set of \(G\) if every vertex in \(V-S\) is adjacent to at least one vertex in \(S\). The domination number \(\gamma(G)\) of \(G\) is the minimum cardinality taken over all dominating sets in \(G\). A dominating set \(S\) of \(G\) is called a complementary perfect dominating set (cpd-set) if the induced subgraph \(\langle V-S \rangle\) has a perfect matching. The complementary perfect domination number, \(\gamma_{cp}(G)\), of \(G\) is the minimum cardinality taken over all cpd-sets in \(G\).
An induced complementary perfect dominating set of a graph (icpd-set) is a dominating set of \(G\) such that the induced subgraph \(\langle V-S \rangle\) has only independent edges. That is, \(\langle V-S \rangle = mK_2\), \(m \geq 1\). The minimum cardinality taken over all such icpd-sets of \(G\) is called the induced complementary perfect domination number of \(G\), and is denoted by \(\gamma_{icp}(G)\).
A subset \(S\) of \(V\) is said to be a complementary connected dominating set (ccd-set) if \(S\) is a dominating set and \(\langle V-S \rangle\) is connected. The complementary connected domination number of a graph is denoted by \(\gamma_{cc}(G)\) and is defined as the minimum number of vertices which form a ccd-set.
It has been proved that \(\gamma_{cp}(G) = n = \gamma_{icp}(G)\) and \(\gamma_{cc}(G) = n-1\) only if \(G\) is a star. And if \(G\) is not a star, then \(\gamma_{cp}, \gamma_{icp}, \gamma_{cc} \leq n-2\). In this paper, we characterize the graphs with \(\gamma_{cc} \leq n-2\), and trees with \(\gamma_{cp} = n-2\) and \(\gamma_{icp} = n-2\).
1970-2025 CP (Manitoba, Canada) unless otherwise stated.