The interlace polynomial of a graph

DOI10.1016/J.JCTB.2004.03.003MaRDI QIDQ705880zbMATH OpenOpenAlexFDO

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)

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)

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.

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

Cites work

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

Cited in

(61)

• A BRACKET POLYNOMIAL FOR GRAPHS, II: LINKS, EULER CIRCUITS AND MARKED GRAPHS
• The adjacency matroid of a graph
• Interlace polynomials for multimatroids and delta-matroids
• The nullity theorem for principal pivot transform
• Entanglement criteria for the bosonic and fermionic induced ensembles
• On the reconstruction of graph invariants
• Interlace polynomials of lollipop and tadpole graphs
• scientific article; zbMATH DE number 6378508 (Why is no real title available?)
• A two-variable interlace polynomial
• Distance Hereditary Graphs and the Interlace Polynomial
• Interlacement in 4-regular graphs: a new approach using nonsymmetric matrices
• 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
• Interlace polynomials of 4n-snowflake graphs
• Graph polynomials and their applications. II: Interrelations and interpretations
• Weighted interlace polynomials
• On the interlace polynomials
• The universal valuation of Coxeter matroids
• Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants
• scientific article; zbMATH DE number 1445310 (Why is no real title available?)
• Interlace polynomials of friendship graphs
• Interlace polynomials of ladder 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
• From matrix pivots to graphs in surfaces: exploring combinatorics through partial duals
• Circle graphs and the cycle double cover conjecture
• The group structure of pivot and loop complementation on graphs and set systems
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• Nullity invariance for pivot and the interlace polynomial
• Eulerian digraphs and toric Calabi-Yau varieties
• Bipartite graphs as polynomials and polynomials as bipartite graphs
• Graph polynomials derived from Tutte-Martin polynomials
• 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
• Signed permutohedra, delta‐matroids, and beyond
• Binary matroids and local complementation
• The transition matroid of a 4-regular graph: an introduction
• On the Tutte and Matching Polynomials for Complete Graphs
• On the interlace polynomials of forests
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Linear Recurrence Relations for Graph Polynomials
• Coding and Cryptography
• Exclusivity structures and graph representatives of local complementation orbits
• On graphs and codes preserved by edge local complementation
• Rank-width and vertex-minors
• K-classes of delta-matroids and equivariant localization
• Binary nullity, Euler circuits and interlace polynomials
• Interlace polynomials: enumeration, unimodality and connections to codes
• Vertex-minors of graphs: a survey
• A BRACKET POLYNOMIAL FOR GRAPHS, III: VERTEX WEIGHTS
• Connection Matrices for MSOL-Definable Structural Invariants
• Random feedback shift registers and the limit distribution for largest cycle lengths
• 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

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)