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

bipartite graphschordal graphsdominationreconfiguration 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

• -graphs of graphs
• 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
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• 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

Cited in

(44)

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

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)