Weighted interlace polynomials

Details Weighted interlace polynomials Weighted interlace polynomials

2008-08-13

arxiv.org/abs/0808.1888v4

Mathematics

Combinatorics

11 pages (v1); 20 pages (v2); 27 pages (v3); 26 pages (v4). Further changes may be made before publication in Combinatorics, P

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Weighted interlace polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Weighted interlace polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Weighted interlace polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-387188