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.