Restrained domination in cubic graphs

Johannes H. Hattingh, Ernst J. Joubert

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

Abstract

Let G=(V,E) be a graph. A set S-V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted γ r (G), is the smallest cardinality of a restrained dominating set of G. A graph G is said to be cubic if every vertex has degree three. In this paper, we study restrained domination in cubic graphs. We show that if G is a cubic graph of order n, then γr(G) ≥ n/4, and characterize the extremal graphs achieving this lower bound. Furthermore, we show that if G is a cubic graph of order n, then γr(G)≤ 5n/11. Lastly, we show that if G is a claw-free cubic graph, then γ r (G)=γ(G).

Original languageEnglish
Pages (from-to)166-179
Number of pages14
JournalJournal of Combinatorial Optimization
Volume22
Issue number2
DOIs
Publication statusPublished - Aug 2011

Keywords

  • Cubic graph
  • Domination
  • Graph
  • Lower bound
  • Restrained domination
  • Upper bound

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

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

Cite this