Simplicity in Eulerian circuits : Uniqueness and safety

Nidia Obscura Acosta; Alexandru I. Tomescu

doi:10.1016/j.ipl.2023.106421

Simplicity in Eulerian circuits : Uniqueness and safety

Nidia Obscura Acosta^*, Alexandru I. Tomescu

^*Corresponding author for this work

Department of Computer Science

University of Helsinki

Research output: Contribution to journal › Article › Scientific › peer-review

2 Citations (Scopus)

123 Downloads (Pure)

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.

Original language	English
Article number	106421
Pages (from-to)	1-5
Number of pages	5
Journal	Information Processing Letters
Volume	183
Early online date	21 Jun 2023
DOIs	https://doi.org/10.1016/j.ipl.2023.106421
Publication status	Published - Jan 2024
MoE publication type	A1 Journal article-refereed

Funding

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 ).

Keywords

BEST theorem
Cut node
Eulerian circuit
Graph Algorithms
Safety

Access to Document

10.1016/j.ipl.2023.106421Licence: CC BY

Simplicity in Eulerian circuits - Uniqueness and safetyFinal published version, 311 KBLicence: CC BY

Cite this

@article{f3a7a218daa944ff88d0851f477428d3,

title = "Simplicity in Eulerian circuits : Uniqueness and safety",

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.",

keywords = "BEST theorem, Cut node, Eulerian circuit, Graph Algorithms, Safety",

author = "\{Obscura Acosta\}, Nidia and Tomescu, \{Alexandru I.\}",

note = "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: {\textcopyright} 2023 The Author(s)",

year = "2024",

month = jan,

doi = "10.1016/j.ipl.2023.106421",

language = "English",

volume = "183",

pages = "1--5",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

}

TY - JOUR

T1 - Simplicity in Eulerian circuits : Uniqueness and safety

AU - Obscura Acosta, Nidia

AU - Tomescu, Alexandru I.

N1 - 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)

PY - 2024/1

Y1 - 2024/1

N2 - 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.

AB - 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.

KW - BEST theorem

KW - Cut node

KW - Eulerian circuit

KW - Graph Algorithms

KW - Safety

UR - https://www.scopus.com/pages/publications/85163791658

U2 - 10.1016/j.ipl.2023.106421

DO - 10.1016/j.ipl.2023.106421

M3 - Article

AN - SCOPUS:85163791658

SN - 0020-0190

VL - 183

SP - 1

EP - 5

JO - Information Processing Letters

JF - Information Processing Letters

M1 - 106421

ER -

Simplicity in Eulerian circuits : Uniqueness and safety

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Combinatorics of Graph Packing and Online Binary Search Trees.

Combinatorics of Graph Packing and Online Binary Search Trees

Cite this

Simplicity in Eulerian circuits : Uniqueness and safety

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Combinatorics of Graph Packing and Online Binary Search Trees.

Combinatorics of Graph Packing and Online Binary Search Trees

Cite this