The difference between the domination number and the minus domination number of a cubic graph (Q1431983): Difference between revisions

The paper concerns the domination number and the minus domination number of a graph. Let \(G\) be an undirected graph with vertex set \(V\). For each \(v\in V\) the symbol \(N[v]\) denotes the closed neighbourhood of \(v\) in \(G\), i.e. the set consisting of \(v\) and of all vertices adjacent to \(v\) in \(G\). Both the mentioned numbers can be defined by means of a certain function on \(V\). If \(f\) is a mapping of \(V\) into a set of numbers and \(S\subseteq V\), then \(f(S)= \sum_{x\in S} f(x)\). Now let \(f: V\to \{0,1\}\). This mapping is called a dominating function on \(G\), if \(f(N[v])\geq 1\) for each \(v\in V\). The weight of \(f\) is \(w(f)= f(V)\). The minimum weight \(w(f)\), taken over all dominating functions \(f\) on \(G\), is called the domination number \(\gamma(G)\) of \(G\). Quite analogously the minus domination number \(\gamma^-(G)\) of \(G\) is defined, using \(f: V\to \{-1,0,1\}\) instead of \(f: V\to \{0,1\}\). Evidently \(\gamma^-(G)\leq\gamma(G)\) for every graph \(G\). The main result of the paper states that for each positive integer \(k\) a cubic (i.e. regular of degree 3) graph \(G\) exists such that \(\gamma(G)- \gamma^-(G)\geq k\).