Graph polynomial
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.
See also
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.
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.