Weighted interlace polynomials

DOI10.1017/S0963548309990381zbMATH Open1216.05059arXiv0808.1888MaRDI QIDQ3557529FDOQ3557529

Authors: L. Traldi 

Publication date: 23 April 2010

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: The interlace polynomials introduced by Arratia, Bollobas and Sorkin extend to invariants of graphs with vertex weights, and these weighted interlace polynomials have several novel properties. One novel property is a version of the fundamental three-term formula q(G)=q(G-a)+q(G^{ab}-b)+((x-1)^{2}-1)q(G^{ab}-a-b) that lacks the last term. It follows that interlace polynomial computations can be represented by binary trees rather than mixed binary-ternary trees. Binary computation trees provide a description of $q(G)$ that is analogous to the activities description of the Tutte polynomial. If $G$ is a tree or forest then these "algorithmic activities" are associated with a certain kind of independent set in $G$. Three other novel properties are weighted pendant-twin reductions, which involve removing certain kinds of vertices from a graph and adjusting the weights of the remaining vertices in such a way that the interlace polynomials are unchanged. These reductions allow for smaller computation trees as they eliminate some branches. If a graph can be completely analyzed using pendant-twin reductions then its interlace polynomial can be calculated in polynomial time. An intuitively pleasing property is that graphs which can be constructed through graph substitutions have vertex-weighted interlace polynomials which can be obtained through algebraic substitutions.

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

Recommendations

• A two-variable interlace polynomial
• On the interlace polynomials of forests
• The interlace polynomial of a graph
• Interlace polynomials
• Graph polynomials from principal pivoting

Mathematics Subject Classification ID

Graph polynomials (05C31) Signed and weighted graphs (05C22)

Cites Work

• A higher invariant for matroids
• A Tutte polynomial for signed graphs
• Circle graph obstructions
• Digraph Decompositions and Eulerian Systems
• Decomposition of Directed Graphs
• Reducing prime graphs and recognizing circle graphs
• Circle graphs and monadic second-order logic
• The interlace polynomial of graphs at \(-1\)
• On Invariants of Graphs with Applications to Knot Theory
• Interlace polynomials
• Distance Hereditary Graphs and the Interlace Polynomial
• A two-variable interlace polynomial
• Multimatroids. III: Tightness and fundamental graphs
• The interlace polynomial of a graph
• Generalized activities and the Tutte polynomial
• A Dichromatic Polynomial for Weighted Graphs and Link Polynomials
• Tutte polynomials computable in polynomial time
• Interval partitions and activities for the greedoid Tutte polynomial
• Series and parallel reductions for the Tutte polynomial

Cited In (9)

• The adjacency matroid of a graph
• Distance Hereditary Graphs and the Interlace Polynomial
• Title not available (Why is that?)
• A two-variable interlace polynomial
• Proving identities on weight polynomials of tiered trees via Tutte polynomials
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• Binary matroids and local complementation
• On the interlace polynomials of forests
• A BRACKET POLYNOMIAL FOR GRAPHS, III: VERTEX WEIGHTS

This page was built for publication: Weighted interlace polynomials

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