Opuscula Math. 33, no. 4 (2013), 763-783
http://dx.doi.org/10.7494/OpMath.2013.33.4.763
Opuscula Mathematica
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.
Mathematics Subject Classification: 05C69.
- Włodzimierz Ulatowski
- Gdańsk University of Technology, Department of Technical Physics and Applied Mathematics, Narutowicza 11/12, 80–952 Gdańsk, Poland
- Received: 2013-02-27.
- Revised: 2013-05-14.
- Accepted: 2013-05-21.
