The interlace polynomial of a graph

DOI10.1016/j.jctb.2004.03.003zbMath1060.05062arXivmath/0209045OpenAlexW1976190799MaRDI QIDQ705880

Richard Arratia, Gregory B. Sorkin, Béla Bollobás

Publication date: 16 February 2005

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

Tutte polynomialBEST theoremKauffman bracketEuler circuitCircle graphCircuit partitionExtremalInterlace graphMartin polynomialMatrix-tree theoremPairing

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Related Items (47)

On the Tutte and Matching Polynomials for Complete Graphs ⋮ A BRACKET POLYNOMIAL FOR GRAPHS, IV: UNDIRECTED EULER CIRCUITS, GRAPH-LINKS AND MULTIPLY MARKED GRAPHS ⋮ Evaluations of Graph Polynomials ⋮ Interlace polynomials of lollipop and tadpole graphs ⋮ The adjacency matroid of a graph ⋮ Interlace polynomials for multimatroids and delta-matroids ⋮ From matrix pivots to graphs in surfaces: exploring combinatorics through partial duals ⋮ Random feedback shift registers and the limit distribution for largest cycle lengths ⋮ Graph reductions, binary rank, and pivots in gene assembly ⋮ Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants ⋮ Interlace polynomials of 4n-snowflake graphs ⋮ Signed permutohedra, delta‐matroids, and beyond ⋮ Nullity invariance for pivot and the interlace polynomial ⋮ Fast evaluation of interlace polynomials on graphs of bounded treewidth ⋮ The nullity theorem for principal pivot transform ⋮ The enumeration of vertex induced subgraphs with respect to the number of components ⋮ The group structure of pivot and loop complementation on graphs and set systems ⋮ Eulerian digraphs and toric Calabi-Yau varieties ⋮ Binary matroids and local complementation ⋮ Random tensor theory: Extending random matrix theory to mixtures of random product states ⋮ On the linear algebra of local complementation ⋮ A BRACKET POLYNOMIAL FOR GRAPHS, III: VERTEX WEIGHTS ⋮ The transition matroid of a 4-regular graph: an introduction ⋮ Weighted Interlace Polynomials ⋮ Circle graphs and monadic second-order logic ⋮ A BRACKET POLYNOMIAL FOR GRAPHS, II: LINKS, EULER CIRCUITS AND MARKED GRAPHS ⋮ Orienting transversals and transition polynomials of multimatroids ⋮ Exclusivity structures and graph representatives of local complementation orbits ⋮ Bipartite graphs as polynomials and polynomials as bipartite graphs ⋮ Interlace polynomials: enumeration, unimodality and connections to codes ⋮ On graphs and codes preserved by edge local complementation ⋮ Distance Hereditary Graphs and the Interlace Polynomial ⋮ Pivots, determinants, and perfect matchings of graphs ⋮ Binary nullity, Euler circuits and interlace polynomials ⋮ Connection Matrices for MSOL-Definable Structural Invariants ⋮ The expansion of a chord diagram and the Tutte polynomial ⋮ Linear Recurrence Relations for Graph Polynomials ⋮ Edge local complementation and equivalence of binary linear codes ⋮ From a zoo to a zoology: Towards a general theory of graph polynomials ⋮ Circle graphs and the cycle double cover conjecture ⋮ Rank-width and vertex-minors ⋮ On the interlace polynomials of forests ⋮ On the reconstruction of graph invariants ⋮ A BRACKET POLYNOMIAL FOR GRAPHS, I ⋮ The universal valuation of Coxeter matroids ⋮ Interlace polynomials of friendship graphs ⋮ Entanglement criteria for the bosonic and fermionic induced ensembles

Cites Work

• Convolution of unimodal distributions can produce any number of modes
• A characterization of circle graphs
• On Tutte polynomials and cycles of plane graphs
• State models and the Jones polynomial
• Isotropic systems
• Graphic presentations of isotropic systems
• On the evaluation at (3,3) of the Tutte polynomial of a graph
• Tutte-Martin polynomials and orienting vectors of isotropic systems
• Approximate string-matching with \(q\)-grams and maximal matches
• Remarkable valuation of the dichromatic polynomial of planar multigraphs
• The coefficients of the Tutte polynomial are not unimodal
• Interlace polynomials
• New results for the Martin polynomial
• Euler circuits and DNA sequencing by hybridization
• Alternating knot diagrams, Euler circuits and the interlace polynomial
• Evaluations of the circuit partition polynomial
• The interlace polynomial of graphs at \(-1\)
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Chromatic polynomials and logarithmic concavity
• Le Polynôme De Martin D'un Graphe Eulerien
• New Invariants in the Theory of Knots
• On the Principal Edge Tripartition of a Graph
• Recognition of Circle Graphs
• Recognizing circle graphs in polynomial time
• An introduction to chromatic polynomials
• On Unicursal Paths in a Network of Degree 4
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The interlace polynomial of a graph