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
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.
- M. Chellali, T.W. Haynes, Trees with unique minimum paired-dominating sets, Ars Combin. 73 (2004), 3-12.
- P. Dorbec, M.A. Henning, J. McCoy, Upper total domination versus upper paired-domination, Quest. Math. 30 (2007), 1-12.
- P. Dorbec, S. Gravier, M.A. Henning, Paired-domination in generalized claw-free graphs, J. Comb. Optim. 14 (2007), 1-7.
- O. Favaron, M.A. Henning, Paired-domination in claw-free cubic graphs, Graphs Comb. 20 (2004), 447-456.
- T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Fundamentals of domination in graphs, Marcel Dekker, New York, 1998.
- T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in graphs: advanced topics, Marcel Dekker, New York, 1998.
- T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998), 199-209.
- M.A. Henning, Graphs with large paired-domination number, J. Comb. Optim. 13 (2007), 61-78.
- J. Raczek, Lower bound on the paired-domination number of a tree, Australas. J. Comb. 34 (2006), 343-347.
- 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.
- Received: 2013-07-01.
- Revised: 2014-02-17.
- Accepted: 2014-02-17.
- Published online: 2014-11-12.
