Skip to content

Counting spanning quasi-trees of ribbon graphs: determinants and #P-completeness

Jul 2026 · arXiv.org · Vol abs/2607.19713 · 0 citations · 48 references
Computer Science Mathematics

Abstract

A quasi-tree of a connected ribbon graph is a spanning ribbon subgraph with exactly one boundary component; quasi-trees play the role of spanning trees in the topological graph theory of embedded graphs. We prove that counting them is #P-complete under polynomial-time Turing reductions, already for bouquets. The proof identifies every nonempty framed chord diagram, up to natural identifications, with a 4-regular map equipped with a distinguished A-trail, in such a way that quasi-trees correspond to A-trails, whose counting is #P-complete by a theorem of Ge and \v{S}tefankovi\v{c}. Through the framed Cohn-Lempel equality the count is also an interlace-polynomial evaluation - $q(H;2,1)$, the number of full-rank induced subgraphs of the looped circle graph $H$ of the diagram - placing it on the line $y=1$ left open in the complexity classification of Bl\"aser and Hoffmann; a cloning argument then makes every fixed rational point of that line, other than the trivial $(1,1)$, #P-hard on looped circle graphs, even when a framed chord representation is supplied. On the tractable side, the same GF(2) model yields short proofs of the known determinantal cases: for orientable ribbon graphs the count is a determinant, essentially the Matrix-Quasi-tree Theorem of Merino, Moffatt and Noble, proved here via Bouchet's principal unimodularity, and for bouquets with exactly one non-orientable loop it is a sum of two orientable determinants, equivalent by a rank-one determinant identity to the determinant formula of Deng, Jin and Yan.

View source

Similar papers

Open access Sep 2026

A Poset-Theoretic Approach to Reduced Cozero-Divisor Graphs of ℤ n and Related Rings

Let R be a finite commutative ring with identity, and let Γ′ᵣ(R) denote its reduced cozero-divisor graph. We organize Γ′ᵣ(R) through the poset Prin*(R) of nonzero proper principal ideals and prove that adjacency is exactly incomparability in this poset. Consequently, cliques correspond to antichains, independent sets c...

Dong-Ze Du · 0 citations
Preprint Oct 2026

Trace-minimal graphs maximizing the number of spanning trees

A classical problem in spectral graph theory is to determine, among all simple graphs with a fixed number of vertices and edges, those that maximize the number of spanning trees. Such graphs are called $t$-optimal. Petingi and Rodr\'iguez [Discr. Math. 244 (2002), 351-373] reduced the construction of infinitely many $t...

Pablo Romero, L. Petingi · 0 citations
Preprint Oct 2026

Linear resolutions of powers of edge ideals of gap-free graphs with matching number four

For a finite simple gap-free graph $G$, let $B(G)$ denote the vertices $v$ for which $G-N_G[v]$ is not co-chordal, and put $C(G)=V(G)\setminus B(G)$. We prove a sufficient condition for all ordinary powers of its edge ideal to have linear resolutions from the second power onward: every induced anticycle of length at le...

Luis Alfredo Dupont García · 0 citations
Preprint Oct 2026

Claw-free perfect graphs are chromatic-choosable

We prove that every claw-free perfect graph $G$ satisfies $\ch(G)=\chi(G)=\omega(G)$. More strongly, if $S$ is a clique of simplicial vertices of $G$ and $k\ge\omega(G)$, every proper precoloring of $S$ extends to a proper coloring of $G$ from arbitrary lists of size $k$ on $V(G)\setminus S$. The proof has three colori...

Suchismita Mishra, N. Narayanan, Umesh Shankar · 0 citations
Preprint Sep 2026

Balanced even cycles in signed graphs:Tur\'an bounds, double covers, and parity obstructions

We study Tur\'an problems for balanced even cycles in simple signed graphs, where signed subgraphs are considered up to switching. For every balanced bipartite signed graph, the signed and ordinary Tur\'an numbers differ by at most a factor of two. Our main structural results concern the underlying graphs that admit a...

Lu-Jia Wang, Xiao-Wei Yu · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.