The interlace polynomial of a graph (Q705880)

The authors define the interlace polynomial \(q(G;x)\) of a finite undirected graph \(G\) by means of a pivot-reduction relation. If \(H= H(C)\) is the interlace graph of an Euler circuit of a 2-in, 2-out digraph \(D\), then \(q(H;1)\) is the number of Euler circuits of \(D\); and if \(G\) is any graph of order \(n\), then \(q(G;2)= 2^n\). The authors establish various properties of \(q(G;x)\) and discuss its connection with the Martin polynomial of interlace graphs. They determine the interlace polynomial for certain simple graphs and answer certain extremal questions. They also discuss, among other things, some conjectures and open problems. The real question, in their opinion, is whether there is an elementary combinatorial interpretation of \(q(G;x)\) in general.