2009/03/25 by Lorenzo Traldi, Traldi, Lorenzo
Computer Science · Mathematics · #05C50 #Combinatorics (math.CO) #FOS: Mathematics #Geometric and Algebraic Topology #Homotopy and Cohomology in Algebraic Topology #math.CO #msc:05C50 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0903.4405
8 pages (v1); 10 pages (v2). Further changes may be made before publication in the European Journal of Combinatorics
openalex publication_date 2009/03/25 · arxiv created 2009/12/31 · arxiv updated 2010/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A theorem of Cohn and Lempel [J. Combin. Theory Ser. A 13 (1972), 83-89] gives an equality relating the number of circuits in a directed circuit partition of a 2-in, 2-out digraph to the GF(2)-nullity of an associated matrix. This equality is essentially equivalent to the relationship between directed circuit partitions of 2-in, 2-out digraphs and vertex-nullity interlace polynomials of interlace graphs. We present an extension of the Cohn-Lempel equality that describes arbitrary circuit partitions in (undirected) 4-regular graphs. The extended equality incorporates topological results that have been of use in knot theory, and it implies that if H is obtained from an interlace graph by attaching loops at some vertices then the vertex-nullity interlace polynomial qN(H) is essentially the generating function for certain circuit partitions of an associated 4-regular graph.