Distance Hereditary Graphs and the Interlace Polynomial
From MaRDI portal
Abstract: 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 �eta 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 �eta 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.
Recommendations
Cites work
- A characterization of circle graphs
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
- A Combinatorial Model for Series-Parallel Networks
- A Contribution to the Theory of Chromatic Polynomials
- A polynomial invariant of graphs on orientable surfaces
- A polynomial of graphs on surfaces
- A proof of a circle graph characterization
- A two-variable interlace polynomial
- Alternating knot diagrams, Euler circuits and the interlace polynomial
- Approximating clique-width and branch-width
- Chordality properties on graphs and minimal conceptual connections in semantic data models
- Circle graph obstructions
- Compatible Euler tours and supplementary Eulerian vectors
- Connectivity and \(\beta\)-invariants of isotropic systems and 4-regular graphs
- Distance-hereditary graphs
- Euler circuits and DNA sequencing by hybridization
- Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
- Evaluations of the circuit partition polynomial
- Exploring the Tutte-Martin connection
- Graph colorings with local constraints -- a survey
- Graph polynomials derived from Tutte-Martin polynomials
- Graphic presentations of isotropic systems
- Identities for circuit partition polynomials, with applications to the Tutte polynomial
- Interlace polynomials
- Isotropic systems
- New results for the Martin polynomial
- On Crapo's Beta Invariant for Matroids
- On the evaluation at (3,3) of the Tutte polynomial of a graph
- Rank-width and vertex-minors
- Reducing prime graphs and recognizing circle graphs
- Remarkable valuation of the dichromatic polynomial of planar multigraphs
- The interlace polynomial of a graph
- The interlace polynomial of graphs at \(-1\)
- Topology of series-parallel networks
- Tutte polynomials computable in polynomial time
- Tutte-Martin polynomials and orienting vectors of isotropic systems
- Unimodularity and circle graphs
Cited in
(12)- On the interlace polynomials of forests
- On graphs and codes preserved by edge local complementation
- Binary nullity, Euler circuits and interlace polynomials
- On polygon numbers of circle graphs and distance hereditary graphs
- On the Galois Lattice of Bipartite Distance Hereditary Graphs
- A graph integral formulation of the circuit partition polynomial
- Weighted interlace polynomials
- The adjacency matroid of a graph
- A tight relation between series-parallel graphs and bipartite distance hereditary graphs
- Interlace polynomials of 4n-snowflake graphs
- Fast evaluation of interlace polynomials on graphs of bounded treewidth
- Isotropic matroids. I: Multimatroids and neighborhoods
This page was built for publication: Distance Hereditary Graphs and the Interlace Polynomial
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5428369)
