On the interlace polynomials of forests

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

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

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
Volume310
Issue number1
DOIs
StatePublished - 6 Jan 2010

    Fingerprint

Keywords

  • Forest
  • Interlace polynomial
  • Tree
  • Vertex weight

Cite this