4.2 Article

Simplicity in Eulerian circuits: Uniqueness and safety

Journal

INFORMATION PROCESSING LETTERS
Volume 183, Issue -, Pages -

Publisher

ELSEVIER
DOI: 10.1016/j.ipl.2023.106421

Keywords

Graph Algorithms; Eulerian circuit; Cut node; Safety; BEST theorem

Ask authors/readers for more resources

This paper presents a new linear-time checkable characterization of directed graphs with a unique Eulerian circuit. The characterization 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. Additionally, the paper proposes a method to compute all maximal safe walks appearing in all Eulerian circuits in linear time.
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.& COPY; 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.2
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available