Signed domination in regular graphs (Q1815329): Difference between revisions

Let \(G\) be a finite, undirected graph without loops or multiple edges. For a vertex \(x\) in \(V(G)\), \(N[x]\) denotes the set consisting of \(x\) and of all vertices adjacent to \(x\). If \(f\) is a function which assigns real numbers to vertices of a graph \(G\) and \(S\subseteq V(G)\), then \(f(S)\) is defined as \(\sum_{x\in S}f(x)\). A signed dominating function \(f\) of a graph \(G\) is defined as a function \(f:V(G)\to\{-1, 1\}\) such that \(\sum_{v\in N[x]}f(v)\geq 1\) for each \(x\in V(G)\). A signed dominating function \(g\) is a minimal signed dominating function if every signed dominating function \(h\) satisfying \(h(v)\leq g(v)\) for every \(v\in V\), is equal to \(g\). The signed domination number of \(G\) is defined as \(\gamma_s(G)=\text{min}\{g(V)\mid g\) a signed dominating function\}. Define \(\Gamma_s(G)=\text{max}\{g(V)\mid g\) a minimal signed dominating function\}. The author shows that if \(G\) is a \(k\)-regular graph, \(k\geq 1\), of order \(n\), then \(\Gamma_s(G)\leq n(k+1)/(k+3)\) if \(k\) is even and \(\Gamma_s(G)\leq n(k+1)^2/(k^2+4k-1)\) if \(k\) is odd. These bounds are sharp and the graphs realizing the equality are described. He also shows that \(\gamma_s\leq n-2\lceil{n\over 8}\rceil\leq {3n\over 4}\) holds for any connected cubic graph other than the Petersen graph.