On a trace formula for counting Eulerian cycles

Abstract

Counting Eulerian cycles in undirected graphs is a classical problem in enumerative combinatorics and is #P-complete in general. We connect this problem with homological spectral graph theory and prove an explicit trace formula for the number of Eulerian cycles. For an Eulerian graph G with m edges and genus g, the number ec(G) is expressed as a signed average of traces of the m-th powers of twisted vertex adjacency matrices A_gamma and twisted edge adjacency matrices B_gamma, indexed by H_1(G,Z/2Z). The formula yields a fixed-parameter tractable exact algorithm with parameter g: after the 2^g twists are fixed, the remaining work is polynomial in the graph size. Since #P-completeness rules out a polynomial-time exact algorithm for arbitrary graphs unless FP=#P, this confines the unavoidable complexity to the homological parameter in a precise sense. Finally, we develop symmetry reductions coming from spectral antisymmetry and graph automorphisms, often decreasing the number of distinct twisted spectra that must be evaluated.

29 pages, 1 figure; revised and substantially expanded version, including complexity analysis, an algorithmic interpretation, applications, and updated references