Reconfiguration graphs for dominating sets
type: Item
instance of: scholarly article
title: Reconfiguration graphs for dominating sets
zbMATH Open document ID: 1482.05246
DOI: 10.1007/978-3-030-77983-2_6
author: Kira Adaricheva
author: Chassidy Bozeman
author: Nancy E. Clarke
author: Ruth Haas
author: Margaret-Ellen Messinger
author: Heather Smith
author: K. Seyffarth
publication date: 2022-02-01T00:00:00Z
review text: If \(G\) is a graph, then the \(k\)-dominating graph \(D_k(G)\) of \(G\) is the graph whose vertices correspond to the dominating sets of \(G\) that have cardinality at most \(k\), two vertices of \(D_k(G)\) being adjacent if and only if the corresponding dominating sets of \(G\) differ by either adding or deleting a single vertex. The introduction of the \(k\)-dominating graphs was motivated by similar studied on graph colorings, by a reconfiguration problem (which asks whether a feasible solution to a problem can be transformed into another by some allowable set of moves, while maintaining feasibility at all steps), and in general to further understand the relationships between dominating sets of a graph. For instance, given dominating sets \(S\) and \(T\), is there a sequence of dominating sets \(S = S_1, S_2,\ldots, S_k = T\) such that each \(S_{i+1}\) is obtained from \(S_i\) by deleting or adding a single vertex? In Section 2 of this chapter, the authors state previous work on reconfiguration of dominating sets. In Section 3, they investigate properties of the dominating graph, \(D(G)\), i.e., the \(k\)-dominating graph when \(k=|V (G)|\). For example, they prove that if \(G\) is a connected graph on \(n\geq 2\) vertices, then \(D(G)\) has diameter \(n\). Also, the graph \(D(G)\) has a cut-vertex if and only if \(G\cong K_{1,n}\) for some natural \(n\). In Section 4, they focus their attention on Hamilton paths of dominating graphs. For the entire collection see [Zbl 1470.05006].
reviewed by: Saeid Alikhani
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 7467664
zbMATH Keywords: domination
zbMATH Keywords: dominating graph
zbMATH Keywords: reconfiguration
MaRDI profile type: Publication
full work available at URL: 978-3-030-77983-2 6
OpenAlex ID: W3204791468
cites work: On k-Total Dominating Graphs
cites work: On the structure of dominating graphs
cites work: Classifying coloring graphs
cites work: Q5422499
cites work: Linear transformations between dominating sets in the TAR-model
cites work: Reconfiguring vertex colourings of 2-trees
cites work: Reconfiguring k-colourings of Complete Bipartite Graphs
cites work: Connectedness of the graph of vertex-colourings
cites work: Gray code numbers for graphs
cites work: A note on \(\gamma\)-graphs
cites work: Reconfiguring minimum dominating sets: the \(\gamma\)-graph of a tree
cites work: γ-graphs of graphs
cites work: Q4198056
cites work: The \(k\)-dominating graph
cites work: Reconfiguring dominating sets in some well-covered and other classes of graphs
cites work: The complexity of dominating set reconfiguration
cites work: Reconfiguration on sparse graphs
cites work: The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree
cites work: On the parameterized complexity of reconfiguration problems
cites work: Q5133651
cites work: A note on some variations of the $\gamma$-graph
cites work: Connected \(k\)-dominating graphs
cites work: Introduction to reconfiguration
cites work: Reconfiguration of dominating sets
Recommended article: Reconfiguration of dominating sets
Recommended article: Reconfiguring dominating sets in some well-covered and other classes of graphs
Recommended article: Q5133651
Recommended article: The Complexity of Dominating Set Reconfiguration
Recommended article: The complexity of dominating set reconfiguration
Recommended article: Reconfiguring dominating sets in minor-closed graph classes
Recommended article: On the parameterized complexity of reconfiguration of connected dominating sets
Recommended article: Q6089671
Recommended article: Reconfiguration graphs of zero forcing sets
description: scientific article; zbMATH DE number 7467664