Perfect Italian domination on planar and regular graphs

DOI10.1016/J.DAM.2020.05.024zbMATH Open1450.05066arXiv1905.06293OpenAlexW3044925268MaRDI QIDQ2197486FDOQ2197486

Juho Lauri, Christodoulos Mitillos

Publication date: 31 August 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A perfect Italian dominating function of a graph $G=(V,E)$ is a function $f:Vo0,1,2$ such that for every vertex $f(v)=0$, it holds that $su{m}_{uinN(v)}f(u)=2$, i.e., the weight of the labels assigned by $f$ to the neighbors of $v$ is exactly two. The weight of a perfect Italian function is the sum of the weights of the vertices. The perfect Italian domination number of $G$, denoted by $gamm{a}_I^p(G)$, is the minimum weight of any perfect Italian dominating function of $G$. While introducing the parameter, Haynes and Henning (Discrete Appl. Math. (2019), 164--177) also proposed the problem of determining the best possible constants $c_{m}athcalG$ such that $gamm{a}_I^p(G)leq{c}_{m}athcalGimesn$ for all graphs of order $n$ when $G$ is in a particular class $mathcalG$ of graphs. They proved that $c_{m}athcalG=1$ when $mathcalG$ is the class of bipartite graphs, and raised the question for planar graphs and regular graphs. We settle their question precisely for planar graphs by proving that $c_{m}athcalG=1$ and for cubic graphs by proving that $c_{m}athcalG=2/3$. For split graphs, we also show that $c_{m}athcalG=1$. In addition, we characterize the graphs $G$ with $gamm{a}_I^p(G)$ equal to 2 and 3 and determine the exact value of the parameter for several simple structured graphs. We conclude by proving that it is NP-complete to decide whether a given bipartite planar graph admits a perfect Italian dominating function of weight $k$.

Full work available at URL: https://arxiv.org/abs/1905.06293

Recommendations

• Perfect Italian domination in graphs: complexity and algorithms
• Perfect Roman domination in regular graphs
• Perfect Italian domination in cographs
• Perfect Italian domination in trees
• Italian domination and perfect Italian domination on Sierpiński graphs

zbMATH Keywords

Italian domination, perfect Italian

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• House of Graphs: a database of interesting graphs
• Fast generation of regular graphs and construction of cages
• Roman domination in graphs.
• Threshold graphs and related topics
• Roman \(\{2 \}\)-domination
• Extremal Problems for Roman Domination
• Planar 3DM is NP-complete
• Fair domination in graphs
• Induced Matchings in Subcubic Graphs
• \(k\)-domination and \(k\)-independence in graphs: A survey
• Efficient algorithms for Roman domination on some classes of graphs
• Defendens Imperium Romanum: A Classical Problem in Military Strategy
• \([1,2]\)-sets in graphs
• Title not available (Why is that?)
• Italian domination in trees
• Title not available (Why is that?)
• Generalized perfect domination in graphs
• Perfect Italian domination in trees
• An Annotated Glossary of Graph Theory Parameters, with Conjectures

Cited In (7)

• Italian domination and perfect Italian domination on Sierpiński graphs
• Global italian domination in graphs
• Perfect Italian domination number of graphs
• Perfect Italian domination on some generalizations of cographs
• Perfect Italian domination in graphs: complexity and algorithms
• Domination parameters of generalized Sierpiński graphs
• Varieties of Roman Domination

Uses Software

• House of Graphs
• GENREG

This page was built for publication: Perfect Italian domination on planar and regular graphs

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