Metraipolis › archive › dc_ca7cb305ea4f

Hamiltonicity of graphs of acyclic orientations and acyclic polynomials — arXiv:2609.02249

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.02249
License (as archived): CC0-1.0
Archived: 2026-10-17T05:33:01.005Z
SHA-256 of the archived text: 40d539a5872a0bbe424990109b1007d5f039e7322616c4d2ff467f02048e6358
Stable URL of this page: https://metraipolis.com/documento/dc_ca7cb305ea4f

How to cite

Hamiltonicity of graphs of acyclic orientations and acyclic polynomials — arXiv:2609.02249 — arXiv (en), https://arxiv.org/abs/2609.02249 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ca7cb305ea4f (Metraipolis archive dc_ca7cb305ea4f, sha256 40d539a5872a0bbe424990109b1007d5f039e7322616c4d2ff467f02048e6358)

BibTeX

@misc{dcca7cb305ea4f,
  title = {Hamiltonicity of graphs of acyclic orientations and acyclic polynomials — arXiv:2609.02249},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.02249},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ca7cb305ea4f; sha256 40d539a5872a0bbe424990109b1007d5f039e7322616c4d2ff467f02048e6358},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.02249. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the graph $\mathcal{AO}(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 $\mathcal{AO}(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 $\mathcal{AO}$-Hamiltonian. Moreover, we give a criterion for the gluing of a multipath on a given graph to preserve $\mathcal{AO}$-Hamiltonicity. Building towards an inductive certification of $\mathcal{AO}$-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 $\mathcal{AO}$-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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-03 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.02249 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T04:59:51.777Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-03?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).