On the interlace polynomials of forests

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

Research output: Contribution to journalArticle

2 Citations (Scopus)

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

Polynomials
Polynomial
Euler circuit
Graph in graph theory
Digraph
Explicit Formula
Path
Generalise
Invariant
Networks (circuits)
Arbitrary
Class

Keywords

  • Forest
  • Interlace polynomial
  • Tree
  • Vertex weight

Cite this

Anderson, C. ; Cutler, J. ; Radcliffe, A. J. ; Traldi, L. / On the interlace polynomials of forests. In: Discrete Mathematics. 2010 ; Vol. 310, No. 1. pp. 31-36.
@article{7308be48d6f5434698e67ba1b752b56e,
title = "On the interlace polynomials of forests",
abstract = "The interlace polynomials were introduced by Arratia, Bollob{\'a}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{\'a}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.",
keywords = "Forest, Interlace polynomial, Tree, Vertex weight",
author = "C. Anderson and J. Cutler and Radcliffe, {A. J.} and L. Traldi",
year = "2010",
month = "1",
day = "6",
doi = "10.1016/j.disc.2009.07.027",
language = "English",
volume = "310",
pages = "31--36",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "1",

}

Anderson, C, Cutler, J, Radcliffe, AJ & Traldi, L 2010, 'On the interlace polynomials of forests', Discrete Mathematics, vol. 310, no. 1, pp. 31-36. https://doi.org/10.1016/j.disc.2009.07.027

On the interlace polynomials of forests. / Anderson, C.; Cutler, J.; Radcliffe, A. J.; Traldi, L.

In: Discrete Mathematics, Vol. 310, No. 1, 06.01.2010, p. 31-36.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the interlace polynomials of forests

AU - Anderson, C.

AU - Cutler, J.

AU - Radcliffe, A. J.

AU - Traldi, L.

PY - 2010/1/6

Y1 - 2010/1/6

N2 - 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.

AB - 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.

KW - Forest

KW - Interlace polynomial

KW - Tree

KW - Vertex weight

UR - http://www.scopus.com/inward/record.url?scp=70350704812&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2009.07.027

DO - 10.1016/j.disc.2009.07.027

M3 - Article

AN - SCOPUS:70350704812

VL - 310

SP - 31

EP - 36

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1

ER -