A tight bound for independent domination of cubic graphs without 4-cycles - Cho, Eun Kyung; Choi, Ilkyoo; Kwon, Hyemin; Park, Boram (Journal of Graph Theory, 2023)
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.
Keywords: 4-cycle; Cubic graph; Dominating sets; Domination number; Independent domination number; Independent dominations; Regular graphs; Tight bound; cubic graph; domination number; independent domination number; regular graph