Opuscula Math. 35, no. 1 (2015), 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

Włodzimierz Ulatowski

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.

Full text (pdf)

1. M. Chellali, T.W. Haynes, Trees with unique minimum paired-dominating sets, Ars Combin. 73 (2004), 3-12.
2. P. Dorbec, M.A. Henning, J. McCoy, Upper total domination versus upper paired-domination, Quest. Math. 30 (2007), 1-12.
3. P. Dorbec, S. Gravier, M.A. Henning, Paired-domination in generalized claw-free graphs, J. Comb. Optim. 14 (2007), 1-7.
4. O. Favaron, M.A. Henning, Paired-domination in claw-free cubic graphs, Graphs Comb. 20 (2004), 447-456.
5. T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Fundamentals of domination in graphs, Marcel Dekker, New York, 1998.
6. T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in graphs: advanced topics, Marcel Dekker, New York, 1998.
7. T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998), 199-209.
8. M.A. Henning, Graphs with large paired-domination number, J. Comb. Optim. 13 (2007), 61-78.
9. J. Raczek, Lower bound on the paired-domination number of a tree, Australas. J. Comb. 34 (2006), 343-347.
10. W. Ulatowski, All graphs with paired-domination number two less than their order, Opuscula Math. 33 (2013) 4, 763-783.
• Włodzimierz Ulatowski
• Gdansk University of Technology, Faculty of Physics and Mathematics, Narutowicza 11/12, 80-233 Gdańsk, Poland
• Communicated by Dalibor Fronček.
• Revised: 2014-02-17.
• Accepted: 2014-02-17.
• Published online: 2014-11-12.