Physical Sciences and Mathematics Commons^™

The K-Dominating Graph, Ruth Haas, Karen Seyffarth

Mathematics Sciences: Faculty Publications

Abstract. Given a graph G, the k-dominating graph of G, D_k(G), is defined to be the graph whose vertices correspond to the dominating sets of G that have cardinality at most k. Two vertices in D_k(G) are adjacent if and only if the corresponding dominating sets of G differ by either adding or deleting a single vertex. The graph D_k(G) aids in studying the reconfiguration problem for dominating sets. In particular, one dominating set can be reconfigured to another by a sequence of single vertex additions and deletions, such that the intermediate set of …