A two-variable interlace polynomial

DOI10.1007/S00493-004-0035-6MaRDI QIDQ558311zbMATH OpenOpenAlexFDO

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

Publication date 5 July 2005

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

Tutte polynomialindependent-set polynomialTutte-Martin polynomial

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Algebraic combinatorics (05E99) Graph theory (05C99)

Abstract: We introduce a new graph polynomial in two variables. This ``interlace polynomial can be computed in two very different ways. The first is an expansion analogous to the state space expansion of the Tutte polynomial; the significant differences are that our expansion is over vertex rather than edge subsets, and the rank and nullity employed are those of an adjacency matrix rather than an incidence matrix. The second computation is by a three-term reduction formula involving a graph pivot; the pivot arose previously in the study of interlacement and Euler circuits in four-regular graphs. We consider a few properties and specializations of the two-variable interlace polynomial. One specialization, the ``vertex-nullity interlace polynomial, is the single-variable interlace graph polynomial we studied previously, closely related to the Tutte-Martin polynomial on isotropic systems previously considered by Bouchet. Another, the ``vertex-rank interlace polynomial, is equally interesting. Yet another specialization of the two-variable polynomial is the independent-set polynomial.

Recommendations

• The interlace polynomial of a graph
• Graph polynomials from principal pivoting
• Interlace polynomials
• Weighted interlace polynomials
• Publication:4952623

Cited in

(35)

• 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
• A graph polynomial for independent sets of bipartite graphs
• Interlace polynomials of lollipop and tadpole graphs
• Distance Hereditary Graphs and the Interlace Polynomial
• On the linear algebra of local complementation
• scientific article; zbMATH DE number 2043365 (Why is no real title available?)
• A multivariate interlace polynomial and its computation for graphs of bounded clique-width
• Interlace polynomials
• Weighted interlace polynomials
• On the interlace polynomials
• Polynomial graph invariants induced from the \(\mathfrak{gl} \)-weight system
• Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants
• scientific article; zbMATH DE number 1445310 (Why is no real title available?)
• A bracket polynomial for graphs. IV: Undirected Euler circuits, graph-links and multiply marked graphs
• Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
• Circle graphs and the cycle double cover conjecture
• Graph polynomials and local graph operations
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• Nullity invariance for pivot and the interlace polynomial
• Circuit partitions and signed interlacement in 4-regular graphs
• A bracket polynomial for graphs. I
• Binary matroids and local complementation
• The transition matroid of a 4-regular graph: an introduction
• On the interlace polynomials of forests
• Polynomials with two values
• From a zoo to a zoology: Towards a general theory of graph polynomials
• Linear Recurrence Relations for Graph Polynomials
• Coding and Cryptography
• Exponential Time Complexity of Weighted Counting of Independent Sets
• Binary nullity, Euler circuits and interlace polynomials
• Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
• The bivariate Ising polynomial of a graph
• Graph polynomials from principal pivoting

This page was built for publication: A two-variable interlace polynomial

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