Proving properties of the edge elimination polynomial using equivalent graph polynomials
From MaRDI portal
Abstract: Averbouch, Godlin and Makowsky define the edge elimination polynomial of a graph by a recurrence relation with respect to the deletion, contraction and extraction of an edge. It generalizes some well-known graph polynomials such as the chromatic polynomial and the matching polynomial. By introducing two equivalent graph polynomials, one enumerating subgraphs and the other enumerating colorings, we show that the edge elimination polynomial of a simple graph is reconstructible from its polynomial deck and that it encodes the degree sequence of an arbitrary graph.
Recommendations
- A Most General Edge Elimination Polynomial
- The covered components polynomial: a new representation of the edge elimination polynomial
- The universal edge elimination polynomial and the dichromatic polynomial
- On the reconstruction of graph invariants
- Polynomial reconstruction of the matching polynomial
Cited in
(9)- Bivariate chromatic polynomials in computer algebra
- A note on a broken-cycle theorem for hypergraphs
- The universal edge elimination polynomial and the dichromatic polynomial
- Closed-form expansions for the universal edge elimination polynomial
- The covered components polynomial: a new representation of the edge elimination polynomial
- On the Tutte and Matching Polynomials for Complete Graphs
- Harary polynomials
- On the matching polynomial of hypergraphs
- A Most General Edge Elimination Polynomial
This page was built for publication: Proving properties of the edge elimination polynomial using equivalent graph polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2869336)
