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

Włodzimierz Ulatowski

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.

Full text (pdf)

• Włodzimierz Ulatowski
• Gdańsk University of Technology, Department of Technical Physics and Applied Mathematics, Narutowicza 11/12, 80–952 Gdańsk, Poland
• Revised: 2013-05-14.
• Accepted: 2013-05-21.