In mathematics, a graph polynomial is a graph invariant whose value is a polynomial. Invariants of this type are studied in algebraic graph theory.[1]
Important graph polynomials include:
- The characteristic polynomial, based on the graph's adjacency matrix.
- The chromatic polynomial, a polynomial whose values at integer arguments give the number of colorings of the graph with that many colors.
- The dichromatic polynomial, a 2-variable generalization of the chromatic polynomial
- The flow polynomial, a polynomial whose values at integer arguments give the number of nowhere-zero flows with integer flow amounts modulo the argument.
- The (inverse of the) Ihara zeta function, defined as a product of binomial terms corresponding to certain closed walks in a graph.
- The Martin polynomial, used by Pierre Martin to study Euler tours
- The matching polynomials, several different polynomials defined as the generating function of the matchings of a graph.
- The reliability polynomial, a polynomial that describes the probability of remaining connected after independent edge failures
- The Tutte polynomial, a polynomial in two variables that can be defined (after a small change of variables) as the generating function of the numbers of connected components of induced subgraphs of the given graph, parameterized by the number of vertices in the subgraph.
- ^ Cite error: The named reference
sdlg
was invoked but never defined (see the help page).