Domination and independent domination in some triangle-free cubic graphs

Abstract

In a graph G = ( V ( G ) , E ( G ) ) , with vertex set V(G) and edge set E(G), a set S ⊆ V ( G ) is said to be dominating if every vertex in V ( G ) ∖ S ( G ) has at least one neighbor in S. The domination number of G, denoted by γ ( G ) , is defined as the minimum cardinality among all dominating sets of V(G). Furthermore, a dominating set S is defined as independent if any two vertices in S are pairwise non-adjacent. The independent domination number of G, denoted by i(G), is the minimum cardinality among all independent dominating sets of G. Determining γ ( G ) and i(G) for an arbitrary graph are NP-hard problems. In this work, we calculate the domination and independent domination numbers of two subclasses of triangle-free cubic graphs.