Domination versus independent domination in cubic graphs

Justin Southey, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

20 Citations (Scopus)

Abstract

A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. If, in addition, S is an independent set, then S is an independent dominating set. The domination number γ(G) of G is the minimum cardinality of a dominating set in G, while the independent domination number i(G) of G is the minimum cardinality of an independent dominating set in G. In this paper we show that if G≠K(3,3) is a connected cubic graph, then i(G)/γ(G)≤4/3. This answers a question posed in Goddard (in press) [6] where the bound of 3/2 is proven. In addition we characterize the graphs achieving this ratio of 4/3.

Original languageEnglish
Pages (from-to)1212-1220
Number of pages9
JournalDiscrete Mathematics
Volume313
Issue number11
DOIs
Publication statusPublished - 2013

Keywords

  • Cubic graphs
  • Domination
  • Independent domination
  • Ratio

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

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

Cite this