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
SN - 0012-365X
VL - 310
SP - 31
EP - 36
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1
ER -