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.
From: Ye Luo [view email]
[v1]
Wed, 5 Feb 2025 06:23:10 UTC (21 KB)
[v2]
Wed, 19 Aug 2026 08:58:58 UTC (26 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。