Characterisation of Graphs on Domination Parameters

Abstract

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 $⟨V-S⟩$ 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 $⟨V-S⟩$ has only independent edges. That is, $⟨V-S⟩=m{K}_2$, $m\ge 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 $⟨V-S⟩$ 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}\le n-2$. In this paper, we characterize the graphs with ${\gamma }_{cc}\le n-2$, and trees with ${\gamma }_{cp}=n-2$ and ${\gamma }_{icp}=n-2$.