Perfect Italian domination on planar and regular graphs (Q2197486): Difference between revisions

Let \(G = (V, E)\) be a graph. A perfect Italian dominating function of a graph \(G\) is a function \(f : V \rightarrow \{0, 1, 2\}\) such that for every vertex \(v\in V\) with \(f(v) = 0\), it holds that \(\sum_{u\in N(v)} f (u) = 2\). The perfect Italian domination number of \(G\), denoted by \(\gamma_I^p(G)\), is the minimum weight of any perfect Italian dominating function of \(G\). For \(k \ge 1\), a \(k\)-fair dominating set of \(G\) is a dominating set \(D\) such that \(|N(v)\cap D| = k\) for every \(v \in V \setminus D\). The \(k\)-fair domination number of \(G\), denoted by \(fd_k(G)\), is the minimum cardinality of a \(k\)-fair dominating set in \(G\). For a graph \(G\), let \(\overline{G}\) be the complement of \(G\). In this paper, there are many interesting results and some of main of them are stated as follows. Theorem 1. For every graph \(G\), it holds that \(\gamma_I^p(G) \le fd_2(G)\). Theorem 2. A connected graph \(G\) with \(\gamma_I^p(G)> 2\) has \(\gamma_I^p(G) = 3\) if and only if \(G\) has a \(2\)-fair dominating set \(D\) of size \(3\). Theorem 3. A connected graph \(G\) with \(\gamma_I^p(G)> 2\) has \(\gamma_I^p(G) = 3\) if and only if \(\overline{G}\) has a perfect dominating set of size \(3\). Theorem 4. There is an infinite family of \(n\)-vertex connected planar graphs \(G\) such that \(\gamma_I^p(G) = n\). Theorem 5. A connected graph \(G\) on \(n\) vertices with maximum degree \(\Delta\) has \(\gamma_I^p(G)\ge 2n/(\Delta + 2)\). Theorem 6. Every connected cubic graph \(G\) with \(n\) vertices has \(\frac{2}{5}n \le \gamma_I^p(G)\le \frac{2}{3}n\). Moreover, these bounds are tight. Theorem 7. Perfect Italian domination is NP-complete for bipartite planar graphs.