## Abstract

For a graph G=(V_{G},E_{G}), a perfect Italian dominating function on G is a function g: V_{G} → {0, 1, 2} satisfying the condition that for each vertex v with g(v)=0, the sum of the function values assigned to the neighbors of v is exactly two, that is, ∑g(u)=2 where the sum is taken over all neighbors of v. The weight of g, denoted by w(g) is defined ∑g(v) where the sum is taken over all v ∈ V_{G}. The perfect Italian domination number of G, denoted γ_{I}^{p}(G), is the minimum weight of a perfect Italian dominating function of G. In this paper, we prove that the perfect Italian domination number of a connected cograph, a graph containing no induced path on four vertices, belongs to {1, 2, 3, 4} or equals to the order of the cograph. We prove that there is no connected cograph with perfect Italian domination number k, where k ∈ {5, 6, 7, 8, 9}. We also show that for any positive integer k, k ∉ {5, 6, 7, 8, 9}, there exists a connected cograph whose perfect Italian domination number is k. Moreover, we devise a linear time algorithm that computes the perfect Italian domination number in cographs.

Original language | English |
---|---|

Article number | 125703 |

Journal | Applied Mathematics and Computation |

Volume | 391 |

DOIs | |

Publication status | Published - 15 Feb 2021 |

## Keywords

- Cographs
- Domination
- Italian domination
- Perfect Italian domination
- Roman domination
- Roman {2}-domination

## ASJC Scopus subject areas

- Computational Mathematics
- Applied Mathematics