On the interlace polynomials of forests

C. Anderson, J. Cutler, A. J. Radcliffe, L. Traldi

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


The interlace polynomials were introduced by Arratia, Bollobás and Sorkin (2004) [3-5]. These invariants generalize to arbitrary graphs some special properties of the Euler circuits of 2-in, 2-out digraphs. Among many other results, Arratia, Bollobás and Sorkin (2004) [3-5] give explicit formulas for the interlace polynomials of certain types of graphs, including paths; it is natural to wonder whether or not it is possible to extend these formulas to larger classes of graphs. We give a combinatorial description of the interlace polynomials of trees and forests.

Original languageEnglish
Pages (from-to)31-36
Number of pages6
JournalDiscrete Mathematics
Issue number1
StatePublished - Jan 6 2010

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


  • Forest
  • Interlace polynomial
  • Tree
  • Vertex weight

Cite this