×

zbMATH — the first resource for mathematics

Perfect Italian domination on planar and regular graphs. (English) Zbl 1450.05066
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.
MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brinkmann, G.; Coolsaet, K.; Goedgebeur, J.; Mélot, H., House of graphs: A database of interesting graphs, Discrete Appl. Math., 161, 1, 311-314 (2013) · Zbl 1292.05254
[2] Caro, Y.; Hansberg, A.; Henning, M., Fair domination in graphs, Discrete Math., 312, 19, 2905-2914 (2012) · Zbl 1251.05121
[3] Chaluvaraju, B.; Chellali, M.; Vidya, K., Perfect k-domination in graphs., Australas. J. Combin., 48, 175-184 (2010) · Zbl 1232.05161
[4] Chaluvaraju, B.; Vidya, K., Generalized perfect domination in graphs, J. Comb. Optim., 27, 2, 292-301 (2014) · Zbl 1290.90081
[5] Chambers, E. W.; Kinnersley, B.; Prince, N.; West, D. B., Extremal problems for Roman domination, SIAM J. Discrete Math., 23, 3, 1575-1586 (2009) · Zbl 1207.05135
[6] Chellali, M.; Favaron, O.; Hansberg, A.; Volkmann, L., \(k\)-DOmination and \(k\)-Independence in graphs: A survey, Graphs Combin., 28, 1, 1-55 (2012) · Zbl 1234.05174
[7] Chellali, M.; Haynes, T. W.; Hedetniemi, S. T.; McRae, A., [1, 2]-sets in graphs, Discrete Appl. Math., 161, 18, 2885-2893 (2013) · Zbl 1287.05098
[8] Chellali, M.; Haynes, T. W.; Hedetniemi, S. T.; McRae, A. A., Roman \(\{ 2 \}\)-domination, Discrete Appl. Math., 204, 22-28 (2016) · Zbl 1333.05217
[9] Cockayne, E. J.; Dreyer, P. A.; Hedetniemi, S. M.; Hedetniemi, S. T., Roman domination in graphs, Discrete Math., 278, 1, 11-22 (2004) · Zbl 1036.05034
[10] Dyer, M. E.; Frieze, A. M., Planar 3DM is NP-complete, J. Algorithms, 7, 2, 174-184 (1986) · Zbl 0606.68065
[11] Fellows, M. R.; Hoover, M. N., Perfect domination, Australas. J. Combin., 3, 141-150 (1991) · Zbl 0761.05091
[12] Gera, R.; Haynes, T. W.; Hedetniemi, S. T.; Henning, M. A., An annotated glossary of graph theory parameters, with conjectures, (Graph Theory (2018), Springer), 177-281 · Zbl 1414.05283
[13] Hansberg, A., Reviewing some results on fair domination in graphs, Electron. Notes Discrete Math., 43, 367-373 (2013)
[14] Haynes, T. W.; Henning, M. A., Perfect Italian domination in trees, Discrete Appl. Math., 260, 164-177 (2019) · Zbl 1409.05148
[15] Henning, M. A.; Klostermeyer, W. F., Italian domination in trees, Discrete Appl. Math., 217, 557-564 (2017) · Zbl 1358.05218
[16] Joos, F.; Rautenbach, D.; Sasse, T., Induced matchings in subcubic graphs, SIAM J. Discrete Math., 28, 1, 468-473 (2014) · Zbl 1293.05295
[17] Liedloff, M.; Kloks, T.; Liu, J.; Peng, S.-L., Efficient algorithms for Roman domination on some classes of graphs, Discrete Appl. Math., 156, 18, 3400-3415 (2008) · Zbl 1180.05113
[18] Mahadev, N. V.R.; Peled, U. N., Threshold graphs and related topics (1995), Elsevier · Zbl 0852.05001
[19] Meringer, M., Fast generation of regular graphs and construction of cages, J. Graph Theory, 30, 2, 137-146 (1999) · Zbl 0918.05062
[20] ReVelle, C. S.; Rosing, K. E., Defendens Imperium Romanum: A Classical Problem in Military Strategy, Amer. Math. Monthly, 107, 7, 585-594 (2000) · Zbl 1039.90038
[21] Stewart, I., Defend the Roman empire!, Sci. Am., 281, 6, 136-138 (1999)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.