Graphs whose Eulerian trails have unique labels
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.02501
curl -X POST /api/v1/records/arxiv/2603.02501/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.02501/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'