On the number of Euler trails in directed graphs

Authors

  • Jakob Jonsson

DOI:

https://doi.org/10.7146/math.scand.a-14370

Abstract

Let G be an Eulerian digraph with all in- and out-degrees equal to 2, and let π be an Euler trail in G. We consider an intersection matrix \boldsymbol {L}(\pi) with the property that the determinant of \boldsymbol{L}(\pi) + \boldsymbol{I} is equal to the number of Euler trails in G; \boldsymbol{I} denotes the identity matrix. We show that if the inverse of \boldsymbol{L}(\pi) exists, then \boldsymbol{L}^{-1}(\pi) = \boldsymbol{L}(\sigma) for a certain Euler trail \sigma in G. Furthermore, we use properties of the intersection matrix to prove some results about how to divide the set of Euler trails in a digraph into smaller sets of the same size.

Downloads

Published

2002-06-01

How to Cite

Jonsson, J. (2002). On the number of Euler trails in directed graphs. MATHEMATICA SCANDINAVICA, 90(2), 191–214. https://doi.org/10.7146/math.scand.a-14370

Issue

Section

Articles