Graphs whose Eulerian trails have unique labels
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.
Fields of Study & Subjects
Advanced Graph Theory Research
Graph Labeling and Dimension Problems
Finite Group Theory Research
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 3 March 2026
- Language
- EN
- Document type
- Preprint