ABSTRACT

The interlace polynomial of a graph arises in a number of settings both theoretical e.g., isotropic systems and applied e.g., DNA sequencing by hybridization. This chapter begins with the most straightforward, that of a recursive method for counting Eulerian circuits in two-in, two-out digraphs arising from an application in DNA sequencing. The interlace polynomial of a simple graph is obtained by generalizing the recursion used to solve this counting problem. The chapter discusses a closed form for the polynomial in terms of its adjacency matrix, the structure of which suggests definitions for analogous polynomials as well as a two-variable generalization. Another context in which the interlace polynomial arises is in isotropic systems, where it appears as a specialization of the Tutte–Martin polynomials, a connection follow by way of the Martin polynomials of 4-regular graphs. The chapter reviews generalizations of the polynomial to square matrices and delta-matroids.