Opuscula Mathematica
Opuscula Math. 35, no. 1 (2015), 127-135

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)
References ▼
  1. [1] M. Chellali, T.W. Haynes, Trees with unique minimum paired-dominating sets, Ars Combin. 73 (2004), 3-12.
  2. [2] P. Dorbec, M.A. Henning, J. McCoy, Upper total domination versus upper paired-domination, Quest. Math. 30 (2007), 1-12.
  3. [3] P. Dorbec, S. Gravier, M.A. Henning, Paired-domination in generalized claw-free graphs, J. Comb. Optim. 14 (2007), 1-7.
  4. [4] O. Favaron, M.A. Henning, Paired-domination in claw-free cubic graphs, Graphs Comb. 20 (2004), 447-456.
  5. [5] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Fundamentals of domination in graphs, Marcel Dekker, New York, 1998.
  6. [6] T.W. Haynes, S.T. Hedetniemi, P.J. Slater (Eds.), Domination in graphs: advanced topics, Marcel Dekker, New York, 1998.
  7. [7] T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998), 199-209.
  8. [8] M.A. Henning, Graphs with large paired-domination number, J. Comb. Optim. 13 (2007), 61-78.
  9. [9] J. Raczek, Lower bound on the paired-domination number of a tree, Australas. J. Comb. 34 (2006), 343-347.
  10. [10] W. Ulatowski, All graphs with paired-domination number two less than their order, Opuscula Math. 33 (2013) 4, 763-783.
About the authors ▼
Włodzimierz Ulatowski
Gdansk University of Technology, Faculty of Physics and Mathematics, Narutowicza 11/12, 80-233 Gdańsk, Poland
About the article ▼
Communicated by Dalibor Fronček.
Received: 2013-07-01.
Revised: 2014-02-17.
Accepted: 2014-02-17.
Published online: 2014-11-12.
Cite this article as ▼
Włodzimierz Ulatowski, The paired-domination and the upper paired-domination numbers of graphs, Opuscula Math. 35, no. 1 (2015), 127-135, http://dx.doi.org/10.7494/OpMath.2015.35.1.127.
Download this article's citation as: