A proof of some Schützenberger-type results for Eulerian paths and circuits on digraphs (Q1335502): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 14:07, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A proof of some Schützenberger-type results for Eulerian paths and circuits on digraphs |
scientific article |
Statements
A proof of some Schützenberger-type results for Eulerian paths and circuits on digraphs (English)
0 references
9 October 1994
0 references
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.
0 references
digraph
0 references
Eulerian path
0 references
Eulerian circuits
0 references