The k-Dominating Graph |
| |
Authors: | R Haas K Seyffarth |
| |
Institution: | 1. Department of Mathematics and Statistics, Smith College, Northampton, MA, 01063, USA 2. Department of Mathematics and Statistics, University of Calgary, Calgary, AB, T2N 1N4, Canada
|
| |
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 vertices at each step is a dominating set if and only if they are in the same connected component of D k (G). In this paper we give conditions that ensure D k (G) is connected. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|