The k-dominating graph

DOI10.1007/S00373-013-1302-3zbMATH Open1294.05122arXiv1209.5138OpenAlexW1973079746MaRDI QIDQ2014712FDOQ2014712

Authors: Ruth Haas, K. Seyffarth 

Publication date: 16 June 2014

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

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.

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

Recommendations

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

zbMATH Keywords

chordal graphsdominationbipartite graphsreconfiguration problems

Mathematics Subject Classification ID

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

Cites Work

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

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
• Title not available (Why is that?)
• Classifying coloring graphs
• 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
• On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets
• Dominating sets reconfiguration under token sliding
• Reconfiguring minimum dominating sets: the \(\gamma\)-graph of a tree
• On dominated graphs
• On k-Total Dominating Graphs
• Reconfiguration graphs of shortest paths
• Reconfiguring minimum dominating sets in trees
• Linear transformations between dominating sets in the TAR-model
• Semitotal domination in claw-free cubic graphs
• Reconfiguring dominating sets in minor-closed graph classes
• 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
• γ-induced-paired dominating graphs of paths and cycles
• Eternal domination: criticality and reachability
• Title not available (Why is that?)
• Reconfiguration of maximum-weight \(b\)-matchings in a graph
• The complexity of dominating set reconfiguration
• Gamma graphs of some special classes of trees
• 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)