Distance Hereditary Graphs and the Interlace Polynomial
| dc.creator | Ellis-Monaghan, Joanna A. | |
| dc.creator | Sarmiento, Irasema | |
| dc.date | 2006-04-04 | |
| dc.date | 2006-04-14 | |
| dc.date.accessioned | 2026-07-07T07:10:32Z | |
| dc.date.available | 2026-07-07T07:10:32Z | |
| dc.description | 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 x^1 in the vertex-nullity interlace polynomial, analogously to the β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 γ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 γ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. | |
| dc.description | 31 pages, 6 figures, minor edits | |
| dc.identifier | https://arxiv.org/abs/math/0604088 | |
| dc.identifier | http://arxiv.org/abs/math/0604088 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/111447 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C38; 05C45 | |
| dc.title | Distance Hereditary Graphs and the Interlace Polynomial | |
| dc.type | text |