The interlace polynomial of a graph

DOI10.1016/J.JCTB.2004.03.003zbMATH Open1060.05062arXivmath/0209045OpenAlexW1976190799MaRDI QIDQ705880FDOQ705880

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

Publication date: 16 February 2005

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

Abstract: Motivated by circle graphs, and the enumeration of Euler circuits, we define a one-variable ``interlace polynomial for any graph. The polynomial satisfies a beautiful and unexpected reduction relation, quite different from the cut and fuse reduction characterizing the Tutte polynomial. It emerges that the interlace graph polynomial may be viewed as a special case of the Martin polynomial of an isotropic system, which underlies its connections with the circuit partition polynomial and the Kauffman brackets of a link diagram. The graph polynomial, in addition to being perhaps more broadly accessible than the Martin polynomial for isotropic systems, also has a two-variable generalization that is unknown for the Martin polynomial. We consider extremal properties of the interlace polynomial, its values for various special graphs, and evaluations which relate to basic graph properties such as the component and independence numbers.

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

Recommendations

• The interlace polynomial of graphs at \(-1\)
• Publication:4952623
• INTERVAL POLYNOMIAL OF GRAPHS
• Interlace polynomials of ladder graphs
• Interlace polynomials
• Interlace polynomials of lollipop and tadpole graphs
• On the interlace polynomials
• scientific article; zbMATH DE number 6378508
• Interlacing Polynomials
• On the Polynomial of a Graph

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)

Cites Work

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

Cited In (61)

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

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

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