Total restrained domination in graphs with minimum degree two

M. A. Henning, J. E. Maritz

Research output: Contribution to journalArticlepeer-review

23 Citations (Scopus)

Abstract

In this paper, we continue the study of total restrained domination in graphs, a concept introduced by Telle and Proskurowksi (Algorithms for vertex partitioning problems on partial k-trees, SIAM J. Discrete Math. 10 (1997) 529-550) as a vertex partitioning problem. A set S of vertices in a graph G = (V, E) is a total restrained dominating set of G if every vertex is adjacent to a vertex in S and every vertex of V {minus 45 degree rule} S is adjacent to a vertex in V {minus 45 degree rule} S. The minimum cardinality of a total restrained dominating set of G is the total restrained domination number of G, denoted by γtr (G). Let G be a connected graph of order n with minimum degree at least 2 and with maximum degree Δ where Δ ≤ n - 2. We prove that if n ≥ 4, then γtr (G) ≤ n - frac(Δ, 2) - 1 and this bound is sharp. If we restrict G to a bipartite graph with Δ ≥ 3, then we improve this bound by showing that γtr (G) ≤ n - frac(2, 3) Δ - frac(2, 9) sqrt(3 Δ - 8) - frac(7, 9) and that this bound is sharp.

Original languageEnglish
Pages (from-to)1909-1920
Number of pages12
JournalDiscrete Mathematics
Volume308
Issue number10
DOIs
Publication statusPublished - 28 May 2008
Externally publishedYes

Keywords

  • Bounds
  • Maximum degree
  • Total restrained domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Total restrained domination in graphs with minimum degree two'. Together they form a unique fingerprint.

Cite this