Eternal Domination and Clique Covering

We study the relationship between the eternal domination number of a graph and its clique covering number. Using computational methods, we show that the smallest graph having its eternal domination number less than its clique covering number has $10$ vertices. This answers a question of Klostermeyer and Mynhardt [Protecting a graph with mobile guards, Appl. Anal. Discrete Math. $10$ $(2016)$, no. $1$, $1-29$]. We also determine the complete set of $10$-vertex and $11$-vertex graphs having eternal domination numbers less than their clique covering numbers. In addition, we study the problem on triangle-free graphs, circulant graphs, planar graphs and cubic graphs. Our computations show that all triangle-free graphs and all circulant graphs of order $12$ or less have eternal domination numbers equal to their clique covering numbers, and exhibit $13$ triangle-free graphs and $2$ circulant graphs of order $13$ which do not have this property. Using these graphs, we describe a method to generate an infinite family of triangle-free graphs and an infinite family of circulant graphs with eternal domination numbers less than their clique covering numbers. Our computations also show that all planar graphs of order $11$ or less, all $3$-connected planar graphs of order $13$ or less and all cubic graphs of order less than $18$ have eternal domination numbers equal to their clique covering numbers. Finally, we show that for any integer $k \geq 2$ there exist infinitely many graphs having domination number and eternal domination number equal to $k$ containing dominating sets which are not eternal dominating sets. This answers another question of Klostermeyer and Mynhardt [Eternal and Secure Domination in Graphs, Topics in domination in graphs, Dev. Math. $64$ $(2020)$, $445-478$, Springer, Cham].