NUK - logo
E-viri
Celotno besedilo
Recenzirano
  • Perfect Italian domination ...
    Banerjee, S.; Henning, Michael A.; Pradhan, D.

    Applied mathematics and computation, 02/2021, Letnik: 391
    Journal Article

    •We study the perfect Italian domination problem on cographs.•For a connected cograph G of order n ≥ 1, γIp(G)∈{1,2,3,4} or γIp(G)=n.•There is no connected cograph with γIp(G)=k, where k  ∈  {5, 6, 7, 8, 9}.•A linear time algorithm that computes γIp(G) for a cograph G is proposed. 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.