Perfect Italian domination in cographs

S. Banerjee, Michael A. Henning, D. Pradhan

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)

Abstract

For a graph G=(VG,EG), a perfect Italian dominating function on G is a function g: VG → {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 ∈ VG. The perfect Italian domination number of G, denoted γIp(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 languageEnglish
Article number125703
JournalApplied Mathematics and Computation
Volume391
DOIs
Publication statusPublished - 15 Feb 2021

Keywords

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

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Perfect Italian domination in cographs'. Together they form a unique fingerprint.

Cite this