Eternal Domination in Split Graphs

Stefan Bard1, Chris Duffy2, Michelle Edwards1, Gary MacGillivray, Feiran Yang1
1Mathematics and Statistics, University of Victoria P.O. Box 1700 STN CSC Victoria, BC, Canada V8W 2Y2.
2Mathematics and Statistics, Dalhousie University 6316 Coburg Road P.O. BOX 15000 Halifax, NS, Canada B3H 4R2

Abstract

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.