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

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)

  • Włodzimierz Ulatowski
  • Gdansk University of Technology, Faculty of Physics and Mathematics, Narutowicza 11/12, 80-233 Gdańsk, Poland
  • Received: 2013-07-01.
  • Revised: 2014-02-17.
  • Accepted: 2014-02-17.
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.