Distance Hereditary Graphs and the Interlace Polynomial

Details Distance Hereditary Graphs and the Interlace Polynomial Distance Hereditary Graphs and the Interlace Polynomial

2006-04-04

arxiv.org/abs/math/0604088v2

Mathematics

Combinatorics

31 pages, 6 figures, minor edits

Scientific paper

The vertex-nullity interlace polynomial of a graph, described by Arratia, Bollob\'as 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\'as and Riordan. We define the \gamma invariant as the coefficient of x^1 in the vertex-nullity interlace polynomial, analogously to the \beta invariant, which is the coefficient of x^1 in the Tutte polynomial. We then turn to distance hereditary graphs, and show that graphs in this class have \gamma invariant of 2^{n+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 \gamma invariant 2, just as the series-parallel graphs are exactly the class of graphs with \beta 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.

Affiliated with

Also associated with

No associations

Rating

Distance Hereditary Graphs and the Interlace Polynomial does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distance Hereditary Graphs and the Interlace Polynomial, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distance Hereditary Graphs and the Interlace Polynomial will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-418736