2006/04/04 by Joanna A. Ellis-Monaghan, Ellis-Monaghan, Joanna A., Irasema Sarmiento +1
Computer Science · Mathematics · #05C38 #05C45 #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.math/0604088
openalex publication_date 2006/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The vertex-nullity interlace polynomial of a graph, described by Arratia, Bollobás and Sorkin as evolving from questions of DNA sequencing, and extended to a two-variable interlace polynomial by the same authors, evokes many open questions. These include relations between the interlace polynomial and the Tutte polynomial and the computational complexity of the vertex-nullity interlace polynomial. Here, we prove that the one-variable vertex-nullity interlace polynomial is in general #P-hard to compute. We also show a relation between the two-variable interlace polynomial and the topological Tutte polynomial of Bollobás and Riordan. We define the γinvariant as the coefficient of x1 in the vertex-nullity interlace polynomial, analogously to the βinvariant, which is the coefficient of x1 in the Tutte polynomial. We then turn to distance hereditary graphs, and show that graphs in this class have γinvariant of 2n+1 when n true twins are added in their construction. We furthermore show that bipartite distance hereditary graphs are exactly the class of graphs with γinvariant 2, just as the series-parallel graphs are exactly the class of graphs with βinvariant 1. In addition, we show that a bipartite distance hereditary graph arises precisely as the circle graph of any Euler circuit in the oriented medial graph of a series-parallel graph. From this we conclude that the vertex-nullity interlace polynomial is polynomial time to compute for bipartite distance hereditry graphs, just as the Tutte polynomial is polynomial time to compute for series-parallel graphs.