Digraphs with exactly one Eulerian tour

MaRDI QIDQ5080345zbMATH OpenFDO

Authors Luz Grisales, Antoine Labelle, Rodrigo Posada, Stoyan Ivanov Dimitrov

Publication date 31 May 2022

Full work available at URL https://arxiv.org/abs/2104.10734, https://cs.uwaterloo.ca/journals/JIS/VOL25/Dimitrov/dim4.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

bijective proofCatalan numberdirected graphEulerian tourlabeled tree

Mathematics Subject Classification ID

Combinatorial identities, bijective combinatorics (05A19) Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: We give two combinatorial proofs of the fact that the number of loopless digraphs on the vertex set $[n]$ with no isolated vertices and with exactly one Eulerian tour up to a cyclic shift is $frac12(n-1)!C_n$, where $C_n$ 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.

Recommendations

• scientific article; zbMATH DE number 1827742
• A proof of some Schützenberger-type results for Eulerian paths and circuits on digraphs
• Euler digraphs
• Compatible Eulerian circuits in \(K_ n^{**}\)
• On the number of Euler trails in directed graphs

Cites work

• Algebraic Combinatorics
• Catalan Numbers

Cited in

(3)

• A proof of some Schützenberger-type results for Eulerian paths and circuits on digraphs
• Dyck-Eulerian digraphs
• scientific article; zbMATH DE number 15460 (Why is no real title available?)

Describes a project that uses

Uses Software

• MathOverflow
• OEIS

This page was built for publication: Digraphs with exactly one Eulerian tour

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5080345)