Graph polynomial
Appearance
In graph theory, a branch of mathematics, a graph polynomial is a graph invariant whose values are polynomials.[1] Important graph polynomials include:
- 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.
- The chromatic polynomial, a polynomial whose values at integer arguments give the number of colorings of the graph with that many colors.
- The matching polynomials, several different polynomials defined as the generating function of the matchings of a graph.
- The (inverse of the) Ihara zeta function, defined as a product of binomial terms corresponding to certain closed walks in a graph.
References
- ^ Shi, Yongtang; Dehmer, Matthias; Li, Xueliang; Gutman, Ivan (2016), Graph Polynomials, Discrete Mathematics and Its Applications, CRC Press, ISBN 9781498755917