2008/08/13 by Lorenzo Traldi, Traldi, Lorenzo
Computer Science · Mathematics · #05C50 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Geometric and Algebraic Topology #math.CO #msc:05C50 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0808.1888
11 pages (v1); 20 pages (v2); 27 pages (v3); 26 pages (v4). Further changes may be made before publication in Combinatorics, Probability and Computing
openalex publication_date 2008/08/13 · arxiv created 2009/06/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(Gab-b)+((x-1)2-1)q(Gab-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.