Independent Domination in Bipartite Cubic Graphs

Christoph Brause, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by i(G), is the minimum cardinality of an independent dominating set. In this paper, we study the following conjecture posed by Goddard and Henning (Discrete Math. 313:839–854, 2013): If G≇ K3 , 3 is a connected, cubic, bipartite graph on n vertices, then i(G)≤411n. Henning et al. (Discrete Appl. Math. 162:399–403, 2014) prove the conjecture when the girth is at least 6. In this paper we strengthen this result by proving the conjecture when the graph has no subgraph isomorphic to K2 , 3.

Original languageEnglish
Pages (from-to)881-912
Number of pages32
JournalGraphs and Combinatorics
Volume35
Issue number4
DOIs
Publication statusPublished - 1 Jul 2019

Keywords

  • Cubic Graphs
  • Domination
  • Independent Domination

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Independent Domination in Bipartite Cubic Graphs'. Together they form a unique fingerprint.

Cite this