A proof of some Schützenberger-type results for Eulerian paths and circuits on digraphs
type: Item
instance of: scholarly article
title: A proof of some Schützenberger-type results for Eulerian paths and circuits on digraphs
zbMATH Open document ID: 0808.05053
DOI: 10.1155/S0161171294000736
author: Byoung-Song Chwe
published in: International Journal of Mathematics and Mathematical Sciences
publication date: 1994-10-09T00:00:00Z
full work available at URL: https://eudml.org/doc/47088
review text: A digraph \(D\) is defined by a sequence of arcs \(\alpha = (a_ 1, a_ 2,\dots, a_ m)\). Multiple arcs and loops are allowed. An Eulerian path (circuit) \(\beta\) of \(D\) is considered as a permutation of \(\alpha\) and it is called even (odd) if \(\beta\) is a composition of an even (odd) number of transpositions. M. P. Schützenberger has proved that in a digraph with \(n\) vertices and \(m\) arcs where \(m > 2n\), the number of even Eulerian circuits equals the number of odd Eulerian circuits; see \textit{C. Berge} [Graphes et hypergraphes (1970; Zbl 0213.257)]. The author establishes the following theorem: If \(m \geq 2n\), then the number of even Eulerian paths equals the number of odd Eulerian paths. The Schützenberger result is obtained as a corollary.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 650821
zbMATH Keywords: digraph
zbMATH Keywords: Eulerian path
zbMATH Keywords: Eulerian circuits
reviewed by: Matúš Harminc
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 650821