@Article{Ulatowski2013,
author = "Ulatowski, Włodzimierz",
title = "All graphs with paired-domination number two less than their order",
journal = "Opuscula Math.",
year = "2013",
volume = "33",
number = "4",
pages = "763--783",
doi = "http://dx.doi.org/10.7494/OpMath.2013.33.4.763",
url = "http://dx.doi.org/10.7494/OpMath.2013.33.4.763",
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",
issn = "1232-9274"
}