Simplicity in Eulerian circuits : Uniqueness and safety

Nidia Obscura Acosta*, Alexandru I. Tomescu

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

55 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 languageEnglish
Article number106421
Pages (from-to)1-5
Number of pages5
JournalInformation Processing Letters
Volume183
Early online date21 Jun 2023
DOIs
Publication statusPublished - Jan 2024
MoE publication typeA1 Journal article-refereed

Keywords

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

Fingerprint

Dive into the research topics of 'Simplicity in Eulerian circuits : Uniqueness and safety'. Together they form a unique fingerprint.

Cite this