Covering Italian domination in graphs

DOI10.1016/J.DAM.2021.08.001MaRDI QIDQ2231776zbMATH OpenOpenAlexFDO

Authors Doost Ali Mojdeh, Abdollah Khodkar, B. Samadi, Ismael G. Yero

Publication date 30 September 2021

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

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

zbMATH Keywords

claw-free graphscovering Italian domination numbervertex cover number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: For a graph $G=(V(G),E(G))$, an Italian dominating function (ID function) of $G$ is a function $f:V(G)ightarrow0,1,2$ such that for each vertex $vinV(G)$ with $f(v)=0$, $f(N(v))geq2$, that is, either there is a vertex $uinN(v)$ with $f(u)=2$ or there are two vertices $x,yinN(v)$ with $f(x)=f(y)=1$. A function $f:V(G)ightarrow0,1,2$ is a covering Italian dominating function (CID function) of $G$ if $f$ is an ID function and $vinV(G)midf(v)eq0$ is a vertex cover set. The covering Italian domination number (CID number) $gamm{a}_{cI}(G)$ is the minimum weight taken over all CID functions of $G$. In this paper, we study the CID number in graphs. We show that the problem of computing this parameter is NP-hard even when restricted to some well-known families of graphs, and find some bounds on this parameter. We characterize the family of graphs for which their CID numbers attain the upper bound twice their vertex cover number as well as all claw-free graphs whose CID numbers attain the lower bound half of their orders. We also give the characterizations of some families of graphs with small or large CID numbers.

Recommendations

• Secure Italian domination in graphs
• Restrained Italian domination in graphs
• Global italian domination in graphs
• Starred Italian domination in graphs
• Italian domination and perfect Italian domination on Sierpiński graphs

Cites work

• scientific article; zbMATH DE number 3166040 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Independence and upper irredundance in claw-free graphs
• On Stanley's chromatic symmetric function and clawfree graphs
• On three outer-independent domination related parameters in graphs
• Outer independent Roman dominating functions in graphs
• Roman \(\{2 \}\)-domination
• Roman domination in graphs.

Cited in

(10)

• Italian domination in rooted product graphs
• From the strong differential to Italian domination in graphs
• Starred Italian domination in graphs
• Restrained Italian domination in graphs
• Italian domination and perfect Italian domination on Sierpiński graphs
• scientific article; zbMATH DE number 7527889 (Why is no real title available?)
• Impact of Vertex Addition on Italian Domination Number
• Global italian domination in graphs
• Outer independent double Italian domination: Complexity, characterization
• On the total version of the covering Italian domination problem

This page was built for publication: Covering Italian domination in graphs

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