Total domination versus paired-domination in regular graphs

Joanna Cyman, Magda Dettlaff, Michael A. Henning, Magdalena Lemanska, Joanna Raczek

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

A subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted ?(G), is the minimum cardinality of a dominating set of G, while the minimum cardinalities of a total dominating set and paired-dominating set are the total domination number, ?t(G), and the paired-domination number, ?pr(G), respectively. For k = 2, let G be a connected k-regular graph. It is known [Schaudt, Total domination versus paired domination, Discuss. Math. Graph Theory 32 (2012) 435–447] that ?pr(G)/?t(G) = (2k)/(k + 1). In the special case when k = 2, we observe that ?pr(G)/?t(G) = 4/3, with equality if and only if G~= C5. When k = 3, we show that ?pr(G)/?t(G) = 3/2, with equality if and only if G is the Petersen graph. More generally for k = 2, if G has girth at least 5 and satisfies ?pr(G)/?t(G) = (2k)/(k + 1), then we show that G is a diameter-2 Moore graph. As a consequence of this result, we prove that for k = 2 and k = 57, if G has girth at least 5, then ?pr(G)/?t(G) = (2k)/(k + 1), with equality if and only if k = 2 and G ~= C5 or k = 3 and G is the Petersen graph.

Original languageEnglish
Pages (from-to)573-586
Number of pages14
JournalDiscussiones Mathematicae - Graph Theory
Volume38
Issue number2
DOIs
Publication statusPublished - 2018

Keywords

  • Domination
  • Paired-domination
  • Total domination

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Total domination versus paired-domination in regular graphs'. Together they form a unique fingerprint.

Cite this