Note on Counting Eulerian Circuits

Abstract

We show that the problem of counting the number of Eulerian circuits in an undirected graph is complete for the class #P.

2 figures

Cited by in corpus (3)

• Chinese Postman Problem on Edge-Colored Multigraphs
• On the class of graphs with strong mixing properties
• Asymptotic behaviour of the number of the Eulerian circuits