The difference between the domination number and the minus domination number of a cubic graph Original Research Article

The closed neighborhood of a vertex subset S of a graph G = (V, E), denoted as N[S], is defined as the union of S and the set of all the vertices adjacent to some vertex of S. A dominating set of a graph G = (V, E) is defined as a set S of vertices such that N[S] = V. The domination number of a graph G, denoted as γ(G), is the minimum possible size of a dominating set of G. A minus dominating function on a graph G = (V, E) is a function g : V → {−1, 0, 1} such that g(N[v]) ≥ 1 for all vertices. The weight of a minus dominating function g is defined as g(V) =ΣvϵVg(v). The minus domination number of a graph G, denoted as γ−(G), is the minimum possible weight of a minus dominating function on G. It is well known that γ−(G) ≤ γ(G). This paper is focused on the difference between γ(G) and γ−(G) for cubic graphs. We first present a graph-theoretic description of γ−(G). Based on this, we give a necessary and sufficient condition for γ(G) −γ−(G) ≥ k. Further, we present an infinite family of cubic graphs of order 18k + 16 and with γ(G) −γ−(G) ≥ k