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.
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· Theoretical and Natural Scie...· 0 citations
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...
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...
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
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...
This work proves NP-completeness for every finite nonempty set of odd lengths, resolving an open problem posed by Amarilli, Lombardo, and Monet (WG 2026).
Hitendra Kumar, Mathieu Mari, R. B. Sandeep· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.