TY  - JOUR
ID  - Ulatowski2013
LB  - Ulatowski2013
AU  - Ulatowski, Włodzimierz
TI  - All graphs with paired-domination number two less than their order
ST  - All graphs with paired-domination number two less than their order
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2013
VL  - 33
IS  - 4
SP  - 763
EP  - 783
DO  - http://dx.doi.org/10.7494/OpMath.2013.33.4.763
UR  - http://dx.doi.org/10.7494/OpMath.2013.33.4.763
AB  - 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\).
KW  - paired-domination
KW  - paired-domination number
SN  - 1232-9274
ER  -