The \(k\)-Dominating Graph

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2013-03
Main Authors: Haas, Ruth, Seyffarth, Karen
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Reconfiguration
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422