All graphs with paired-domination number two less than their order

Abstract

Let \(G=(V,E)\) be a graph with no isolated vertices. A set \(S\subseteq V\) is a paired-dominating set of \(G\) if every vertex not in \(S\) is adjacent with some vertex in \(S\) and the subgraph induced by \(S\) contains a perfect matching. The paired-domination number \(\gamma_{p}(G)\) of \(G\) is defined to be the minimum cardinality of a paired-dominating set of \(G\). Let \(G\) be a graph of order \(n\). In [Paired-domination in graphs, Networks 32 (1998), 199-206] Haynes and Slater described graphs \(G\) with \(\gamma_{p}(G)=n\) and also graphs with \(\gamma_{p}(G)=n-1\). In this paper we show all graphs for which \(\gamma_{p}(G)=n-2\).

Keywords

• paired-domination
• paired-domination number