Semitotal domination in graphs

Wayne Goddard, Michael A. Henning, Charles A. McPillan

Research output: Contribution to journalArticlepeer-review

45 Citations (Scopus)

Abstract

In this paper we introduce a parameter that is squeezed between arguably the two most important domination parameters, namely the domination number and the total domination number. We define a set S of vertices in a graph G with no isolated vertices to be a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number, denoted by γt2(G), is the minimum cardinality of a semitotal dominating set of G. We show that if G is a connected graph on n > 4 vertices, then γt2(G) < n/2y and we characterize the trees and graphs of minimum degree 2 achieving this bound.

Original languageEnglish
Pages (from-to)67-81
Number of pages15
JournalUtilitas Mathematica
Volume94
Publication statusPublished - Jul 2014

Keywords

  • Domination
  • Graph
  • Semitotal domination
  • Total domination

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Semitotal domination in graphs'. Together they form a unique fingerprint.

Cite this