The interlace polynomial of a graph (Q705880): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q656146 |
||
Property / reviewed by | |||
Property / reviewed by: John W. Moon / rank | |||
Revision as of 08:31, 20 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The interlace polynomial of a graph |
scientific article |
Statements
The interlace polynomial of a graph (English)
0 references
16 February 2005
0 references
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.
0 references
Pairing
0 references
Interlace graph
0 references
Circle graph
0 references
Euler circuit
0 references
Circuit partition
0 references
Matrix-tree theorem
0 references
BEST theorem
0 references
Martin polynomial
0 references
Tutte polynomial
0 references
Kauffman bracket
0 references
Extremal
0 references