Independent domination in subcubic graphs

A. Akbari, S. Akbari, A. Doosthosseini, Z. Hadizadeh, Michael A. Henning, A. Naraghi

Research output: Contribution to journalArticlepeer-review

5 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 independent domination number i(G) of G is the minimum cardinality of an independent dominating set in G. In Goddard and Henning (Discrete Math 313:839–854, 2013) conjectured that if G is a connected cubic graph of order n, then i(G)≤38n, except if G is the complete bipartite graph K3 , 3 or the 5-prism C5□K2. Further they construct two infinite families of connected cubic graphs with independent domination three-eighths their order. In this paper, we provide a new family of connected cubic graphs G of order n such that i(G)=38n. We also show that if G is a subcubic graph of order n with no isolated vertex, then i(G)≤12n, and we characterize the graphs achieving equality in this bound.

Original languageEnglish
Pages (from-to)28-41
Number of pages14
JournalJournal of Combinatorial Optimization
Volume43
Issue number1
DOIs
Publication statusPublished - Jan 2022

Keywords

  • Cubic graph
  • Independent domination
  • Subcubic graph

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 'Independent domination in subcubic graphs'. Together they form a unique fingerprint.

Cite this