A tight bound for independent domination of cubic graphs without 4-cycles

Abstract

Given a graph (Figure presented.), a dominating set of (Figure presented.) is a set (Figure presented.) of vertices such that each vertex not in (Figure presented.) has a neighbor in (Figure presented.). Let (Figure presented.) denote the minimum size of a dominating set of (Figure presented.). The independent domination number of (Figure presented.), denoted (Figure presented.), is the minimum size of a dominating set of (Figure presented.) that is also independent. We prove that if (Figure presented.) is a cubic graph without 4-cycles, then (Figure presented.), and the bound is tight. This result improves upon two results from two papers by Abrishami and Henning. Our result also implies that every cubic graph (Figure presented.) without 4-cycles satisfies (Figure presented.), which supports a question asked by O and West.