Hamilton Paths in Dominating Graphs of Trees and Cycles

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-02
Main Authors: Adaricheva, Kira, Heather Smith Blake, Bozeman, Chassidy, Clarke, Nancy E, Haas, Ruth, Messinger, Margaret-Ellen, Seyffarth, Karen
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Trees (mathematics)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 \(n\not\equiv 0 \pmod 4\).
ISSN:2331-8422