M. E. Messinger ; A. Porter - Eulerian $k$-dominating reconfiguration graphs

dmtcs:13438 - Discrete Mathematics & Theoretical Computer Science, January 14, 2025, vol. 27:2 - https://doi.org/10.46298/dmtcs.13438
Eulerian $k$-dominating reconfiguration graphsArticle

Authors: M. E. Messinger ; A. Porter

    For a graph $G$, the vertices of the $k$-dominating graph, denoted $\mathcal{D}_k(G)$, correspond to the dominating sets of $G$ with cardinality at most $k$. Two vertices of $\mathcal{D}_k(G)$ are adjacent if and only if the corresponding dominating sets in $G$ can be obtained from one other by adding or removing a single vertex of $G$. Since $\mathcal{D}_k(G)$ is not necessarily connected when $k < |V(G)|$, much research has focused on conditions under which $\mathcal{D}_k(G)$ is connected and recent work has explored the existence of Hamilton paths in the $k$-dominating graph. We consider the complementary problem of determining the conditions under which the $k$-dominating graph is Eulerian. In the case where $k = |V(G)|$, we characterize those graphs $G$ for which $\mathcal{D}_k(G)$ is Eulerian. In the case where $k$ is restricted, we determine for a number of graph classes, the conditions under which the $k$-dominating graph is Eulerian.


    Volume: vol. 27:2
    Section: Graph Theory
    Published on: January 14, 2025
    Accepted on: December 16, 2024
    Submitted on: April 18, 2024
    Keywords: Mathematics - Combinatorics,05C45, 05C69

    Consultation statistics

    This page has been seen 69 times.
    This article's PDF has been downloaded 39 times.