A tight bound for independent domination of cubic graphs without 4‐cycles
Eun‐Kyung Cho, Ilkyoo Choi, Hyemin Kwon, Boram Park
Abstract
Abstract Given a graph , a dominating set of is a set of vertices such that each vertex not in has a neighbor in . Let denote the minimum size of a dominating set of . The independent domination number of , denoted , is the minimum size of a dominating set of that is also independent. We prove that if is a cubic graph without 4‐cycles, then , 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 without 4‐cycles satisfies , which supports a question asked by O and West.
Topics & Concepts
CombinatoricsMathematicsCubic graphDominating setVertex (graph theory)Independent setGraphDomination analysisUpper and lower boundsDiscrete mathematicsLine graphVoltage graphMathematical analysisAdvanced Graph Theory ResearchLimits and Structures in Graph TheoryComplexity and Algorithms in Graphs