Such more general graph polynomials have been studied in even larger generality using the notions of delta-matroids and multimatroids in. In particular, the assembly polynomial can be seen as a special case of the bracket polynomial. These graph polynomials are defined for arbitrary simple graphs instead of circle graphs, and can thus be seen as generalizations of the assembly and rearrangement polynomials that we considered in this chapter. This leads to the notions of the interlace polynomial (which was originally motivated by DNA sequencing by hybridization), the bracket polynomial for graphs, and the Tutte-Martin polynomial. Therefore, the assembly and rearrangement polynomials of this chapter can be defined directly for circle graphs instead of signed DOWs. This is observed in for the special case of the assembly polynomial. It is well known that if two DOWs have a common circle graph, then the four-regular graphs corresponding to these two DOWs have the same transition polynomial.
Note that distinct DOWs may have a common circle graph, for example, the circle graphs of DOWs 1 2 3 4 4 3 2 1 and 1 1 2 2 3 3 4 4 both consist of four isolated vertices because they have no interlaced symbols. In this way, one naturally associates a simple graph, called a circle graph, to a DOW: the vertices are the symbols of w and there is an edge between two symbols if and only if these symbols are interlaced. We call a pair of symbols p, q interlaced in a DOW w, if w is of the form w = ⋯ p⋯ q⋯ p⋯ q⋯. This chapter introduced and studied basic properties of two graph polynomials motivated by DNA rearrangements, the assembly and the rearrangement polynomial, which are both specializations of the (weighted) transition polynomial.ĭOWs have appeared often in graph theory. Masahico Saito, in Algebraic and Combinatorial Computational Biology, 2019 3.6 Generalizations