pith. sign in

arxiv: 2502.17227 · v3 · submitted 2025-02-24 · 🧮 math.CO

On Pancyclicity in a Mixed Model for Domination Reconfiguration

Margaret-Ellen Messinger , Logan Pipes This is my paper

Pith reviewed 2026-05-23 02:23 UTC · model grok-4.3

classification 🧮 math.CO
keywords pancyclicitydomination reconfigurationTARS-graphtoken addition/removaltoken slidingtreescomplete graphsgraph joins
0
0 comments X

The pith

Mixing token addition and sliding makes domination reconfiguration graphs pancyclic for trees, complete graphs and their joins.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the TARS-graph on the dominating sets of G, with edges present under either the token addition/removal rule or the token sliding rule. It establishes that this graph is pancyclic whenever G is a tree, a complete graph, or a complete multipartite graph. The authors further show that pancyclicity is preserved under the join operation: if the TARS-graphs of G and H are pancyclic, then so is the TARS-graph of G ∨ H. This matters because the pure TAR graph on dominating sets is never Hamiltonian, so the targeted addition of sliding edges produces cycles of every length.

Core claim

For the listed graph classes, the TARS-graph is pancyclic. If the TARS-graphs of G and H are pancyclic, then so is the TARS-graph of their join G ∨ H.

What carries the argument

The TARS-graph on dominating sets, with adjacency from either TAR or TS reconfiguration rules.

If this is right

  • TARS-graphs of trees are pancyclic.
  • TARS-graphs of complete graphs are pancyclic.
  • TARS-graphs of complete multipartite graphs are pancyclic.
  • Pancyclicity is preserved under the join operation.
  • The question remains open whether every TARS-graph is pancyclic.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the result holds more generally, small additions of sliding edges would guarantee rich cycle structures in many domination reconfiguration graphs.
  • The join-preservation property could be used to build larger pancyclic examples from smaller ones.
  • One could test the open question by checking small graphs outside the listed classes for missing cycle lengths.

Load-bearing premise

The specific token-sliding edges added to the TAR graph are enough to fill in all missing cycle lengths for the given classes of graphs.

What would settle it

A computation showing that the TARS-graph of a particular tree lacks a cycle of some length k between 3 and the number of vertices.

Figures

Figures reproduced from arXiv: 2502.17227 by Logan Pipes, Margaret-Ellen Messinger.

Figure 1
Figure 1. Figure 1: The TARS-graph of K1,3 where the vertices in each dominating set are coloured red. We provide several relevant definitions in the coming paragraphs, but we refer the reader to [3] for any undefined graph-theoretic terms. A graph G on n vertices is pancyclic if, for every integer ℓ satisfying 3 ≤ ℓ ≤ n, G exhibits a cycle of length ℓ. That is, if a graph has a cycle of every possible length up to and includ… view at source ↗
Figure 2
Figure 2. Figure 2: The binary-reflected Gray code on 5 bits, read column-wis [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Operation A (left) and Operation B (right). [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A schematic diagram of the cycles used in the proof of Theo [PITH_FULL_IMAGE:figures/full_fig_p013_4.png] view at source ↗
read the original abstract

A new model for domination reconfiguration is introduced which combines the properties of the preexisting token addition/removal (TAR) and token sliding (TS) models. The vertices of the TARS-graph correspond to the dominating sets of $G$, where two vertices are adjacent if and only if they are adjacent via either the TAR reconfiguration rule or the TS reconfiguration rule. While the domination reconfiguration graph obtained by using only the TAR rule (sometimes called the dominating graph) will never have a Hamilton cycle, we show that for some classes of graphs $G$, by adding a relatively small number of token sliding edges, the resulting graph is not only hamiltonian, but is in fact pancyclic. In particular, if the underlying graphs are trees, complete graphs, or complete multipartite graphs, we show that their TARS-graphs will be pancyclic. Notably, we prove that if the TARS-graphs of $G$ and $H$ are pancyclic, then the TARS-graph of the join $G \vee H$ will also be pancyclic. We conclude by posing the question: Are all TARS-graphs pancyclic?

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper defines the TARS-graph on the dominating sets of G by taking the union of the TAR edges and a selection of TS edges. It asserts that this graph is pancyclic whenever G is a tree, a complete graph, or a complete multipartite graph, and proves that pancyclicity is preserved under the join operation G ∨ H. The manuscript ends by asking whether every TARS-graph is pancyclic.

Significance. If the stated pancyclicity theorems hold, the work supplies the first explicit families of graphs whose mixed reconfiguration graphs are pancyclic and demonstrates a closure property under joins. This supplies concrete positive instances contrasting with the known non-Hamiltonicity of pure TAR domination graphs and offers a structural tool for building larger examples.

major comments (3)
  1. [Abstract / tree case] The pancyclicity claim for trees (stated in the abstract and presumably proved in the body) rests on the addition of a small number of TS edges, yet no explicit description of those edges, no induction hypothesis on the lengths of cycles, and no verification that every added edge joins two dominating sets appear in the supplied text.
  2. [Join closure] The join-closure argument (abstract) asserts that pancyclicity of TARS(G) and TARS(H) implies pancyclicity of TARS(G ∨ H), but supplies no case analysis on dominating sets that contain vertices from both summands, no description of the induced TAR and TS edges across the join, and no argument ruling out gaps in cycle lengths.
  3. [Complete and complete-multipartite cases] The pancyclicity statements for complete graphs and complete multipartite graphs likewise assert the existence of proofs but contain no explicit edge sets, no enumeration of dominating sets, and no check that the added TS edges produce cycles of every integer length up to the order of the TARS-graph.
minor comments (2)
  1. [Abstract] The abstract claims the TARS-graph is 'not only hamiltonian, but is in fact pancyclic' without first recalling that the pure TAR graph is never Hamiltonian; a brief reminder would clarify the contrast.
  2. [Introduction] Notation for the TARS-graph is introduced without an explicit definition of which TS edges are retained; a formal definition paragraph would aid readability.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each point below and will revise the manuscript to supply the requested explicit details and case analyses.

read point-by-point responses

  1. Referee: [Abstract / tree case] The pancyclicity claim for trees (stated in the abstract and presumably proved in the body) rests on the addition of a small number of TS edges, yet no explicit description of those edges, no induction hypothesis on the lengths of cycles, and no verification that every added edge joins two dominating sets appear in the supplied text.

    Authors: We agree that the tree-case argument in Section 3 would benefit from greater explicitness. The revised manuscript will contain an explicit listing of the added TS edges, a clearly stated induction hypothesis on cycle lengths, and a direct verification that each added edge connects two dominating sets. revision: yes

  2. Referee: [Join closure] The join-closure argument (abstract) asserts that pancyclicity of TARS(G) and TARS(H) implies pancyclicity of TARS(G ∨ H), but supplies no case analysis on dominating sets that contain vertices from both summands, no description of the induced TAR and TS edges across the join, and no argument ruling out gaps in cycle lengths.

    Authors: The join-closure proof will be expanded to include a case analysis on dominating sets that intersect both summands, an explicit description of the TAR and TS edges that cross the join, and a separate argument confirming that cycles of every admissible length are realized. revision: yes

  3. Referee: [Complete and complete-multipartite cases] The pancyclicity statements for complete graphs and complete multipartite graphs likewise assert the existence of proofs but contain no explicit edge sets, no enumeration of dominating sets, and no check that the added TS edges produce cycles of every integer length up to the order of the TARS-graph.

    Authors: These sections will be revised to list the added TS edges explicitly, enumerate the relevant dominating sets when helpful, and verify that the resulting graph contains cycles of every integer length between 3 and its order. revision: yes

Circularity Check

0 steps flagged

No circularity; pancyclicity results are direct proofs from model definition and graph class structure

full rationale

The paper defines the TARS-graph by combining TAR and TS rules on dominating sets, then proves pancyclicity for trees, complete graphs, and complete multipartite graphs plus join closure. These claims rest on explicit edge additions and case analysis for the listed classes rather than any self-definition, fitted parameter renamed as prediction, or load-bearing self-citation. No derivation step reduces to its own inputs by construction; the central results are independent of prior author work and are presented as verifiable graph-theoretic arguments. The open question at the end further indicates the work does not presuppose its own conclusions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claims rest on standard graph-theoretic definitions of dominating sets and the two reconfiguration rules; the only new object is the TARS-graph itself.

axioms (1)
  • standard math Standard definitions of dominating sets, TAR reconfiguration, and TS reconfiguration from prior graph theory literature.
    These definitions are invoked to construct the TARS-graph and to state the pancyclicity claims.
invented entities (1)
  • TARS-graph no independent evidence
    purpose: Mixed reconfiguration graph whose edges come from either TAR or TS moves.
    Newly defined in the paper as the central object of study.

pith-pipeline@v0.9.0 · 5726 in / 1211 out tokens · 71758 ms · 2026-05-23T02:23:34.313269+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    Adaricheva, C

    K. Adaricheva, C. Bozeman, N.E. Clarke, R. Haas, M.E. Messinger , K. Seyffarth, H. Smith, Reconfiguration graphs for dominating sets (2021). In: D. Ferrero, L. Hogben, S.R. Kingan and G.L. Matthews Eds., Research Trends in Graph Theory and Applications , Springer International Publishing, 119–135

    work page 2021

  2. [2]

    Adaricheva, C

    K. Adaricheva, C. Bozeman, N.E. Clarke, R. Haas, M.E. Messinger , K. Seyffarth, H. Smith Blake, Hamilton paths in dominating graphs of trees and cycles, Graphs and Combinatorics 38(6): 174 (2022). 13

    work page 2022

  3. [3]

    Bondy, U.S.R

    J.A. Bondy, U.S.R. Murty, Graph Theory, GTM 244, Springer, Berlin (2008)

    work page 2008

  4. [4]

    Brouwer, P

    A. Brouwer, P. Csorba, L. Schrijver, The number of dominating sets of a finite graph is odd, preprint (2009) https://www.win.tue.nl/~aeb/preprints/domin4a.pdf

    work page 2009

  5. [5]

    Connelly, K

    E. Connelly, K. Hutson, S. Hedetniemi, T.W. Haynes, A Note on γ-Graphs, AKCE International Journal of Graphs and Combinatorics 8(1) (2011) 23–31

    work page 2011

  6. [6]

    Fricke, S.M

    G. Fricke, S.M. Hedetniemi, S.T. Hedetniemi, K.R. Hutson, γ-graphs of graphs, Discus- siones Mathematicae Graph Theory 31 (2011) 517–531

    work page 2011

  7. [7]

    R. Haas, K. Seyffarth, The k-dominating graph, Graphs and Combinatorics 30 (2014) 609–617

    work page 2014

  8. [8]

    M¨ utze, Combinatorial Gray codes—an updated survey, The Electronic Journal of Combinatorics 30(3) (2023) #DS26

    T. M¨ utze, Combinatorial Gray codes—an updated survey, The Electronic Journal of Combinatorics 30(3) (2023) #DS26

    work page 2023

  9. [9]

    Mynhardt, S

    C.M. Mynhardt, S. Nasserasr, Reconfiguration of colourings an d dominating sets in graphs (2020). In: F. Chung, R. Graham, F. Hoffman, L. Hogben, R.C. Mullin and D.B. West, eds. 50 years of combinatorics, graph theory, and computing , Florida, CRC Press, 171–187

    work page 2020

  10. [10]

    Nishimura, Introduction to reconfiguration, Algorithms 11( 4) 52 (2018)

    N. Nishimura, Introduction to reconfiguration, Algorithms 11( 4) 52 (2018)

    work page 2018

  11. [11]

    Shih, C.K

    Y.K. Shih, C.K. Lin, J. Tan, L.H. Hsu, The bipanpositionable bipancy clic property of the hypercube, Computers & Mathematics with Applications 58 (200 9) 1722–1724

    work page

  12. [12]

    Pipes, A mixed model for domination reconfiguration (2024) M ount Allison University, Undergraduate honours thesis

    L. Pipes, A mixed model for domination reconfiguration (2024) M ount Allison University, Undergraduate honours thesis. 14

    work page 2024