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.
  • Received: 2013-07-01.
  • Revised: 2014-02-17.
  • Accepted: 2014-02-17.
  • Published online: 2014-11-12.
Opuscula Mathematica - cover

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:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.