Covering Italian domination in graphs

For a graph G = (V (G), E (G)), an Italian dominating function (ID function) of G is a function f : V (G) → {0, 1, 2} such that for each vertex v ∈ V(G) with f (v) = 0, f (N (v)) ≥ 2, that is, either there is a vertex u → N (v) with f (u) = 2 or there are two vertices x, u → N (v) with f (x) = f (y)...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2021-12, Vol.304, p.324-331
Main Authors: Khodkar, Abdollah, Mojdeh, Doost Ali, Samadi, Babak, Yero, Ismael G.
Format: Article
Language:English
Subjects:
Apexes
Graphs
Lower bounds
Mathematical functions
Minimum weight
Parameters
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For a graph G = (V (G), E (G)), an Italian dominating function (ID function) of G is a function f : V (G) → {0, 1, 2} such that for each vertex v ∈ V(G) with f (v) = 0, f (N (v)) ≥ 2, that is, either there is a vertex u → N (v) with f (u) = 2 or there are two vertices x, u → N (v) with f (x) = f (y) = 1. A function f: V (G) →{0,1,2} is a covering Italian dominating function (CID function) of G if f is an ID function and {v ∈ V (G)| f (v) ≠ 0} is a vertex cover set. The covering Italian domination number (CID number) γ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 CID numbers. →γ ∈
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2021.08.001