Some remarks on domination in cubic graphs

Let \(G\) be a finite, undirected graph with no loops or multiple edges. The vertex set of a graph \(G\) is denoted by \(V(G)\). For a vertex \(x\) in \(V(G)\), \(N[x]\) denotes the set consisting of \(x\) and 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\Sigma=\{-1, 1\}\) such that \(\sum_{v\in N[x]}f(v)\geq 1\) for each \(x\in V(G)\). A minus dominating function \(f\) can be defined similar to above except that \(\Sigma=\{-1, 0, 1\}\). A majority dominating function \(f\) is a function \(f:V(G)\to\{-1, 1\}\) such that \(\sum_{v\in N[x]}f(v)\geq 1\) for at least \({|V(G)|\over 2}\) vertices of \(G\). The minimum of \(f(V(G))\) over all signed (minus, majority) dominating functions \(f\) of a graph \(G\) is called the signed (minus, majority) domination number of \(G\) and is denoted by \(\gamma_s(G)\) \((\gamma^{-}(G), \gamma_{\max}(G))\). The author studies these three types of domination numbers for the case in which \(G\) is a cubic graph. The author proves an upper bound for \(\gamma_s(G)\) and lower bounds for \(\gamma^-(G)\) and \(\gamma_{\max}(G)\), in terms of the order of the cubic graph \(G\).

Recommendations

Cites work

Cited in

(28)

This page was built for publication: Some remarks on domination in cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1815324)