Perfect Italian domination on planar and regular graphs

DOI10.1016/J.DAM.2020.05.024MaRDI QIDQ2197486zbMATHOpenAlexFDO

Authors Juho Lauri, Christodoulos Mitillos

Publication date 31 August 2020

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

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

zbMATH Keywords

Italian domination, perfect Italian

Mathematics Subject Classification ID

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

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$.

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

Cites work

• scientific article; zbMATH DE number 91051 (Why is no real title available?)
• An annotated glossary of graph theory parameters, with conjectures
• Defendens Imperium Romanum: A Classical Problem in Military Strategy
• Efficient algorithms for Roman domination on some classes of graphs
• Extremal problems for roman domination
• Fair domination in graphs
• Fast generation of regular graphs and construction of cages
• Generalized perfect domination in graphs
• House of Graphs: a database of interesting graphs
• Induced matchings in subcubic graphs
• Italian domination in trees
• Perfect Italian domination in trees
• Perfect \(k\)-domination in graphs
• Planar 3DM is NP-complete
• Roman \(\{2 \}\)-domination
• Roman domination in graphs.
• Threshold graphs and related topics
• \([1,2]\)-sets in graphs
• \(k\)-domination and \(k\)-independence in graphs: A survey

Cited in

(10)

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

Describes a project that uses

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)