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

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