Graphs whose Eulerian trails have unique labels

Donggyu Kim, Rose McCarty, Caleb McFarland

Abstract

Consider an undirected graph whose edges are labeled invertibly in a group. When does every Eulerian trail from one fixed vertex to another have the same label? We give a precise structural answer to this question. Essentially, we show that each ``$3$-connected part'' is labeled over a group which is isomorphic to $\mathbb{Z}_2^k$ for some $k$. We also show that the algorithmic problem admits a polynomial-time reduction to the word problem for the group.
BibTeX
@misc{kim2026graphs,
  author = {Donggyu Kim and Rose McCarty and Caleb McFarland},
  title = {{Graphs whose Eulerian trails have unique labels}},
  year = {2026},
  eprint = {2603.02501},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.02501},
}

Loading related content...

Figure