Global Domination Stable Trees

Elizabeth Marie Still1, Teresa W.Haynes1
1Department of Mathematics and Statistics East Tennessee State University Johnson City, TN 37614-0002 USA

Abstract

A set of vertices in a graph \( G \) is a global dominating set of \( G \) if it dominates both \( G \) and its complement \( \overline{G} \). The minimum cardinality of a global dominating set of \( G \) is the global domination number of \( G \). We explore the effects of graph modifications (edge removal, vertex removal, and edge addition) on the global domination number. In particular, for each graph modification, we study the global domination stable trees, that is, the trees whose global domination number remains the same upon the modification. We characterize these stable trees having small global domination numbers.

Keywords: Dominating set; global dominating set; globa] domination stable. AMS subject classification: 05C69