Journal of Integer Sequences, Vol. 25 (2022), Article 22.3.8

Digraphs With Exactly One Eulerian Tour


Luz Grisales
Massachusetts Institute of Technology
Cambridge, MA 02139
USA

Antoine Labelle
McGill University
Montréal, QC H3A 0G4
Canada

Rodrigo Posada
Massachusetts Institute of Technology
Cambridge, MA 02139
USA

Stoyan Dimitrov
University of Illinois at Chicago
Chicago, IL 60607
USA

Abstract:

We give two combinatorial proofs of the fact that the number of loopless directed graphs (digraphs) with n non-isolated vertices and with exactly one Eulerian tour up to a cyclic shift is ½(n—1)!Cn, where Cn denotes the n-th Catalan number. We construct a bijection with a set of labeled rooted plane trees and with a set of valid parenthesis arrangements.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequence A102693.)

Received May 26 2021; revised versions received June 4 2021; August 24 2021; February 10 2022. Published in Journal of Integer Sequences, March 27 2022.

Return to Journal of Integer Sequences home page