Perfect Italian domination in cographs

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

Applied Mathematics and Computation, 2021, vol. 391, issue C

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.

Keywords: Domination; Italian domination; Roman domination; Roman {2}-domination; Perfect Italian domination; Cographs (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300320306561
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:391:y:2021:i:c:s0096300320306561

DOI: 10.1016/j.amc.2020.125703

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().