Simplicity in Eulerian circuits : Uniqueness and safety
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2024-01
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
5
1-5
1-5
Series
Information Processing Letters, Volume 183
Abstract
An Eulerian circuit in a directed graph is one of the most fundamental Graph Theory notions. Detecting if a graph G has a unique Eulerian circuit can be done in polynomial time via the BEST theorem by de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte (1941–1951) [15,16] (involving counting arborescences), or via a tailored characterization by Pevzner, 1989 (involving computing the intersection graph of simple cycles of G), both of which thus rely on overly complex notions for the simpler uniqueness problem. In this paper we give a new linear-time checkable characterization of directed graphs with a unique Eulerian circuit. This is based on a simple condition of when two edges must appear consecutively in all Eulerian circuits, in terms of cut nodes of the underlying undirected graph of G. As a by-product, we can also compute in linear-time all maximal safe walks appearing in all Eulerian circuits, for which Nagarajan and Pop proposed in 2009 [12] a polynomial-time algorithm based on Pevzner characterization.Description
Funding Information: We are very grateful to the anonymous reviewers who helped improved the presentation of this paper. This work was partially funded by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No. 851093 , SAFEBIO) and partially by the Academy of Finland (grants No. 322595 , 328877 , 314284 and 335715 ). Publisher Copyright: © 2023 The Author(s)
Keywords
BEST theorem, Cut node, Eulerian circuit, Graph Algorithms, Safety
Other note
Citation
Obscura Acosta, N & Tomescu, A I 2024, ' Simplicity in Eulerian circuits : Uniqueness and safety ', Information Processing Letters, vol. 183, 106421, pp. 1-5 . https://doi.org/10.1016/j.ipl.2023.106421