Preprint
Oct 2026
Perfect Italian Domination on and Near Split Graphs: Algorithms, Hardness, and Approximation
A perfect Italian dominating function assigns a label from $\{0,1,2\}$ to each vertex so that the labels in the neighborhood of every zero-labeled vertex sum to exactly two. Although the associated decision problem (PID) is NP-complete on chordal graphs, the complexity status on split graphs remains open. We give an $O...
B. AnandBabuN, Ashwin Jacob, S. ManjushaM et al.
· 0 citations