On the number of Euler trails in directed graphs

Jakob Jonsson

Abstract


Let $G$ be an Eulerian digraph with all in- and out-degrees equal to 2, and let $\pi$ 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.

Full Text:

PDF


DOI: http://dx.doi.org/10.7146/math.scand.a-14370

Refbacks

  • There are currently no refbacks.
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.
OK


ISSN 0025-5521 (print) ISSN 1903-1807 (online)

Hosted by the Royal Danish Library