A note on graphs with large girth and small minus domination number (Q1283810): Difference between revisions

An undirected graph \(G\) with vertex set \(V(G)\) is considered. If \(v\in V(G)\), then \(N[v]\) denotes the closed neighborhood of \(v\) in \(G\), i.e. the set consisting of \(v\) and of all vertices which are adjacent to \(v\) in \(G\). If \(f\) is a function which maps \(V(G)\) into a set of numbers and \(S\subseteq V(G)\), then \(f(S)=\sum_{x\in S}f(x)\). A function \(f:V(G)\to\{-1,0,1\}\) is called a minus dominating function in \(G\), if \(f(N[v])\geq 1\) for each \(v\in V(G)\). The minimum value of \(f(V(G))\), taken over all minus dominating functions \(f\) in \(G\), is the minus domination number \(\gamma^-(G)\) of \(G\). The girth \(\text{gir}(G)\) of \(G\) is the minimum length of a circuit in \(G\). The main theorem of the paper states that for every negative integer \(k\) and positive integer \(m\geq 3\) there exists a connected graph \(G\) with \(\text{gir}(G)=m\) and \(\gamma^-(G)\leq k\).