Perfect Italian domination on planar and regular graphs (Q2197486)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Perfect Italian domination on planar and regular graphs |
scientific article |
Statements
Perfect Italian domination on planar and regular graphs (English)
0 references
31 August 2020
0 references
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.
0 references
Italian domination, perfect Italian
0 references