Binary nullity, Euler circuits and interlace polynomials

DOI10.1016/J.EJC.2011.02.004zbMATH Open1227.05168arXiv0903.4405OpenAlexW2151838441MaRDI QIDQ2275481FDOQ2275481

Authors: L. Traldi 

Publication date: 9 August 2011

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: 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 $q_N(H)$ is essentially the generating function for certain circuit partitions of an associated 4-regular graph.

Full work available at URL: https://arxiv.org/abs/0903.4405

Recommendations

• On the interlace polynomials
• Publication:4952623
• Distance Hereditary Graphs and the Interlace Polynomial
• The interlace polynomial of a graph
• Interlace polynomials

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Exact enumeration problems, generating functions (05A15) Graph polynomials (05C31)

Cites Work

• Virtual knot theory
• Title not available (Why is that?)
• Cycle decomposition by disjoint transpositions
• A matrix for computing the Jones polynomial of a knot
• INTRODUCTION TO GRAPH-LINK THEORY
• A BRACKET POLYNOMIAL FOR GRAPHS, II: LINKS, EULER CIRCUITS AND MARKED GRAPHS
• VASSILIEV KNOT INVARIANTS COMING FROM LIE ALGEBRAS AND 4-INVARIANTS
• A bracket polynomial for graphs. I
• Chords in a circle and linear algebra over GF(2)
• On the product of certain permutations
• Title not available (Why is that?)
• A multivariate interlace polynomial and its computation for graphs of bounded clique-width
• Interlace polynomials
• Title not available (Why is that?)
• On the number of Euler trails in directed graphs
• Title not available (Why is that?)
• A two-variable interlace polynomial
• The interlace polynomial of a graph
• A few weight systems arising from intersection graphs
• Cycle decomposition by transpositions
• On a formula for the number of Euler trails for a class of digraphs
• An alternative formula for the number of Euler trails for a class of digraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• \(J\)-invariants of plane curves and framed chord diagrams
• Title not available (Why is that?)

Cited In (12)

• A parity map of framed chord diagrams
• The adjacency matroid of a graph
• On the linear algebra of local complementation
• Graph-links: nonrealizability, orientation, and Jones polynomial
• Parity in knot theory and graph-links
• Nullity invariance for pivot and the interlace polynomial
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• The transition matroid of a 4-regular graph: an introduction
• Sorting by reversals and the theory of 4-regular graphs
• A BRACKET POLYNOMIAL FOR GRAPHS, IV: UNDIRECTED EULER CIRCUITS, GRAPH-LINKS AND MULTIPLY MARKED GRAPHS
• Nullity-based matroid of rough sets and its application to attribute reduction
• Matroids, delta-matroids and embedded graphs

This page was built for publication: Binary nullity, Euler circuits and interlace polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2275481)