Resource title

The interlace polynomial: a new graph polynomial

Resource image

image for OpenScout resource :: The interlace polynomial: a new graph polynomial

Resource description

We define a new graph polynomial, the interlace polynomial, for any undirected graph. Also, we show how to count Euler circuits and circuitdecompositions for any directed or undirected Eulerian graph, by a straightforward reduction formula. For 2-in, 2-out directed graphs D, any Euler circuit induces an undirected "interlace" graph H, and there is a close relationship between the number of circuit decompositions of D and the interlace polynomial of H. We explore this relationship, and properties of the interlace polynomial in general.

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

Resource resource URL

http://eprints.lse.ac.uk/35856/

Resource license