Perfect Italian domination in cographs

作者：

Highlights：

• 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.

摘要

•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.

论文关键词：Domination,Italian domination,Roman domination,Roman {2}-domination,Perfect Italian domination,Cographs

论文评审过程：Received 26 May 2020, Revised 15 September 2020, Accepted 20 September 2020, Available online 7 October 2020, Version of Record 7 October 2020.

论文官网地址：https://doi.org/10.1016/j.amc.2020.125703