The interlace polynomial: a new graph polynomial
Richard Arratia, Béla Bollobás, Gregory B. Sorkin · 2000
We define a new graph polynomial, the interlace polynomial, for any undirected graph. One of our main results is that the polynomial, specified by an intricate recursion relation, is well-defined; in the absence of a direct interpretation of the polynomial, this remains mysterious. The interlace polynomial is not a special case of the Tutte polynomial, nor do we know of any other graph polynomial to which it can be reduced. For 2-in, 2-out directed graphs D, any Euler circuit induces an undirected "interlace" graph H. In this setting, the interlace polynomial q(H) is equal to the Martin polynomial m(D), a variant of the circuit partition polynomial. There is another connection, between the Kauffman brackets of a link diagram, the Martin polynomial, and in turn the interlace polynomial. We explore other properties of the interlace polynomial, such as its relations with the component number and independence number of a graph, its extremal values, and its values for various classes of g...