Eternal Domination in Split Graphs

The eternal domination number of a split graph is shown to equal either its domination number, or its domination number plus one. A characterization of the split graphs which achieve equality in either instance is given. It is shown that the problem of deciding whether the domination number of a Hamiltonian split graph is at most a given integer \(k\) is NP-complete, as is the problem of deciding whether the eternal domination number of a Hamiltonian split graph is at most a given integer \(k\). Finally, the problem of computing the eternal domination number is shown to be polynomial for any subclass of split graphs for which the domination number can be computed in polynomial time, in particular for strongly chordal split graphs.