Hamiltonicity of graphs of acyclic orientations and acyclic polynomials

@misc{muhlherr2026hamiltonicity,
  title = {{Hamiltonicity of graphs of acyclic orientations and acyclic polynomials}},
  author = {Leonie Mühlherr and Germain Poullot},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.02249},
  eprint = {2609.02249},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.02249},
}

TY  - UNPB
TI  - Hamiltonicity of graphs of acyclic orientations and acyclic polynomials
AU  - Leonie Mühlherr
AU  - Germain Poullot
PY  - 2026
DA  - 2026/09/17
PB  - arXiv
DO  - 10.48550/arxiv.2609.02249
UR  - https://arxiv.org/abs/2609.02249
AB  - We study the graph 𝒜𝒪(G) of acyclic orientations of a graph G. Two acyclic orientations are adjacent in this graph if they disagree on the orientation of a single arc. In particular, we focus on the Hamiltonicity of the graphs 𝒜𝒪(G). Using two methods of pattern lacing which generalize the zig-zag method of Brenner, Cardinal, McConville, Merino and Mütze, we characterize which multipaths are 𝒜𝒪-Hamiltonian. Moreover, we give a criterion for the gluing of a multipath on a given graph to preserve 𝒜𝒪-Hamiltonicity. Building towards an inductive certification of 𝒜𝒪-Hamiltonicity via the (open) ear decomposition of 2-connected graphs, we propose three ways of gluing several multipaths to a given graph. In addition, we define the acyclic polynomials to encapsulate both the number of acyclic orientations of a graph and the "parity problem" proposed by Savage, Squire and West: if −1 is not a root of the acyclic polynomial of G, then G is not 𝒜𝒪-Hamiltonian. We explore numerous properties of the acyclic polynomials, proving that they are not instances of the famous Tutte-Whitney polynomials, but that they too exhibit a partial deletion-contraction phenomenon.
ER  -