Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Graph polynomial
open-in-new
<p>In mathematics, a graph polynomial is a <a href="/facts/Graph_property/bjuIvgb1">graph invariant</a> whose value is a <a href="/facts/Polynomial/Lzak8VVx">polynomial</a>. Invariants of this type are studied in <a href="/facts/Algebraic_graph_theory/5HNDPx8g">algebraic graph theory</a>. Important graph polynomials include: </p> <ul><li>The <a href="/facts/Characteristic_polynomial/7m8roDqo">characteristic polynomial</a>, based on the graph's <a href="/facts/Adjacency_matrix/jYXNhYGs">adjacency matrix</a>.</li> <li>The <a href="/facts/Chromatic_polynomial/dvr4Hyz9">chromatic polynomial</a>, a polynomial whose values at integer arguments give the number of colorings of the graph with that many colors.</li> <li>The <a href="/facts/Dichromatic_polynomial/RMzCMxTQ">dichromatic polynomial</a>, a 2-variable generalization of the chromatic polynomial</li> <li>The <a href="/facts/Flow_polynomial/RMzCMxTQ">flow polynomial</a>, a polynomial whose values at integer arguments give the number of <a href="/facts/Nowhere-zero_flow/NYW9vQhk">nowhere-zero flows</a> with integer flow amounts modulo the argument.</li> <li>The (inverse of the) <a href="/facts/Ihara_zeta_function/1FJ8MMr9">Ihara zeta function</a>, defined as a product of binomial terms corresponding to certain closed walks in a graph.</li> <li>The Martin polynomial, used by Pierre Martin to study <a href="/facts/Euler_tour/4l2G67c7">Euler tours</a></li> <li>The <a href="/facts/Matching_polynomial/w9crFDN9">matching polynomials</a>, several different polynomials defined as the <a href="/facts/Generating_function/K7UVjnjL">generating function</a> of the <a href="/facts/Matching_(graph_theory)/s0pUJ7hd">matchings</a> of a graph.</li> <li>The <a href="/facts/Reliability_polynomial/RMzCMxTQ">reliability polynomial</a>, a polynomial that describes the probability of remaining connected after independent edge failures</li> <li>The <a href="/facts/Tutte_polynomial/RMzCMxTQ">Tutte polynomial</a>, 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 <a href="/facts/Induced_subgraph/G3EUC0MQ">induced subgraphs</a> of the given graph, parameterized by the number of vertices in the subgraph.</li></ul>