STRUCTURE OF k-TOTAL DOMINATING GRAPHS

Given a graph G, the k-total dominating graph of G, D t k (G), is defined to be the graph whose vertices correspond to the total dominating sets of G that have car- dinality at most k. Two vertices in D t k (G) are adjacent if and only if the corresponding total dominating sets of G differ by either adding or deleting a single vertex. The graph D t k (G) aids in studying the reconfiguration problem for total dominating sets. In par- ticular, one total dominating set can be reconfigured to another by a sequence of single vertex additions and deletions, such that the intermediate set of vertices at each step is a total dominating set if and only if they are in the same connected component of D t k (G). In this paper we study the k-total dominating graph of a graph.