Hamilton paths in dominating graphs of trees and cycles

DOI10.1007/S00373-022-02579-8zbMATH Open1502.05115arXiv2112.04448OpenAlexW4306294676MaRDI QIDQ2093102FDOQ2093102

Kira Adaricheva, Margaret-Ellen Messinger, Chassidy Bozeman, Nancy E. Clarke, Ruth Haas, Heather Smith Blake, K. Seyffarth

Publication date: 4 November 2022

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

Abstract: The dominating graph of a graph $H$ has as its vertices all dominating sets of $H$, with an edge between two dominating sets if one can be obtained from the other by the addition or deletion of a single vertex of $H$. In this paper we prove that the dominating graph of any tree has a Hamilton path. We also show how a result about binary strings leads to a proof that the dominating graph of a cycle on $n$ vertices has a Hamilton path if and only if $notequiv0pmod4$.

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

zbMATH Keywords

dominationreconfigurationHamilton paths

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The \(k\)-dominating graph
• Gray code numbers for graphs
• Introduction to reconfiguration
• Minimal change list for Lucas strings and some graph theoretic consequences
• Reconfiguring vertex colourings of 2-trees
• Reconfiguring k-colourings of Complete Bipartite Graphs

Cited In (2)

• Isomorphisms and properties of TAR graphs for zero forcing and other \(X\)-set parameters
• TSP tour domination and Hamilton cycle decompositions of regular digraphs

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Hamiltonian cycles in covering graphs of trees 👍 👎
• Hamiltonian paths in Cayley graphs 👍 👎
• Hamiltonian Paths and Cycles in Planar Graphs 👍 👎
• Hamiltonian paths and hamiltonian connectivity in graphs 👍 👎
• Hamiltonian cycles and dominating cycles passing through a linear forest 👍 👎
• Hamiltonian cycles in covering graphs of trees 👍 👎

This page was built for publication: Hamilton paths in dominating graphs of trees and cycles

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