The k-dominating graph

DOI10.1007/S00373-013-1302-3MaRDI QIDQ2014712zbMATH OpenOpenAlexFDO

Authors Ruth Haas, K. Seyffarth

Publication date 16 June 2014

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.5138

zbMATH Keywords

chordal graphsdominationbipartite graphsreconfiguration problems

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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.

Recommendations

• Reconfiguration graphs for dominating sets
• On k-Total Dominating Graphs
• Connected \(k\)-dominating graphs

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Chordal graphs and upper irredundance, upper domination and independence
• Connectedness of the graph of vertex-colourings
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Graph theory
• Gray code numbers for graphs
• Normal hypergraphs and the perfect graph conjecture
• On the complexity of reconfiguration problems
• Reconfiguration of List Edge-Colorings in a Graph
• The canonical coloring graphs of trees and cycles
• \(\gamma\)-graphs of graphs

Cited in

(36)

• Irredundance trees of diameter 3
• Reconfiguring vertex colourings of 2-trees
• On the parameterized complexity of reconfiguration of connected dominating sets
• Reasons to fall (more) in love with combinatorial reconfiguration
• Classifying coloring graphs
• scientific article; zbMATH DE number 2192183 (Why is no real title available?)
• Connected \(k\)-dominating graphs
• Reconfiguration on nowhere dense graph classes
• γ-Paired dominating graphs of lollipop, umbrella and coconut graphs
• Isomorphisms and properties of TAR graphs for zero forcing and other \(X\)-set parameters
• Irredundance graphs
• TS-reconfiguration of dominating sets in circle and circular-arc graphs
• Reconfiguring dominating sets in some well-covered and other classes of graphs
• Introduction to reconfiguration
• Dominating sets reconfiguration under token sliding
• Reconfiguring minimum dominating sets: the -graph of a tree
• On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets
• On dominated graphs
• On k-Total Dominating Graphs
• Reconfiguration graphs of shortest paths
• Reconfiguring minimum dominating sets in trees
• Reconfiguring dominating sets in minor-closed graph classes
• Linear transformations between dominating sets in the TAR-model
• Semitotal domination in claw-free cubic graphs
• Reconfiguration graphs for dominating sets
• On reconfiguration graphs: an abstraction
• γ-paired dominating graphs of cycles
• On the structure of dominating graphs
• The complexity of dominating set reconfiguration
• Eternal domination: criticality and reachability
• γ-induced-paired dominating graphs of paths and cycles
• The complexity of dominating set reconfiguration
• Reconfiguration of maximum-weight b-matchings in a graph
• Gamma graphs of some special classes of trees
• scientific article; zbMATH DE number 7764115 (Why is no real title available?)
• Hamilton paths in dominating graphs of trees and cycles

This page was built for publication: The \(k\)-dominating graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2014712)