Graph polynomial
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 flow polynomial, a polynomial whose values at integer arguments give the number of nowhere-zero flows with integer flow amounts modulo the argument.
- 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
This set index article includes a list of related items that share the same name (or similar names).
If an internal link incorrectly led you here, you may wish to change the link to point directly to the intended article.
If an internal link incorrectly led you here, you may wish to change the link to point directly to the intended article.