Opuscula Math. 35, no. 1 (), 127-135
http://dx.doi.org/10.7494/OpMath.2015.35.1.127
Opuscula Mathematica

# The paired-domination and the upper paired-domination numbers of graphs

Abstract. In this paper we continue the study of paired-domination in graphs. A paired-dominating set, abbreviated PDS, of a graph $$G$$ with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of $$G$$, denoted by $$\gamma_{p}(G)$$, is the minimum cardinality of a PDS of $$G$$. The upper paired-domination number of $$G$$, denoted by $$\Gamma_{p}(G)$$, is the maximum cardinality of a minimal PDS of $$G$$. Let $$G$$ be a connected graph of order $$n\geq 3$$. Haynes and Slater in [Paired-domination in graphs, Networks 32 (1998), 199-206], showed that $$\gamma_{p}(G)\leq n-1$$ and they determine the extremal graphs $$G$$ achieving this bound. In this paper we obtain analogous results for $$\Gamma_{p}(G)$$. Dorbec, Henning and McCoy in [Upper total domination versus upper paired-domination, Questiones Mathematicae 30 (2007), 1-12] determine $$\Gamma_{p}(P_n)$$, instead in this paper we determine $$\Gamma_{p}(C_n)$$. Moreover, we describe some families of graphs $$G$$ for which the equality $$\gamma_{p}(G)=\Gamma_{p}(G)$$ holds.
Keywords: paired-domination, paired-domination number, upper paired-domination number.
Mathematics Subject Classification: 05C69.