Tutte polynomial
E1025362
The Tutte polynomial is a fundamental graph invariant in combinatorics that encodes extensive structural information about a graph, unifying and generalizing numerous other graph invariants such as the chromatic and flow polynomials.
Statements (50)
| Predicate | Object |
|---|---|
| instanceOf |
combinatorial invariant
ⓘ
graph invariant ⓘ polynomial invariant ⓘ |
| alsoKnownAs | dichromate ⓘ |
| appliesTo |
looped graphs
ⓘ
multigraphs ⓘ planar graphs ⓘ |
| captures |
deletion–contraction structure of a graph
ⓘ
rank and nullity of edge subsets ⓘ |
| codomain | bivariate polynomials over integers ⓘ |
| computationalComplexity | #P-hard to evaluate at most points ⓘ |
| dependsOn |
edge set
ⓘ
graph ⓘ vertex set ⓘ |
| domain |
graphs
ⓘ
matroids ⓘ |
| encodes |
connected subgraph information
ⓘ
cut structure information ⓘ cycle structure information ⓘ spanning tree information ⓘ |
| field |
combinatorics
ⓘ
graph theory ⓘ |
| generalizes |
Jones polynomial of alternating links
NERFINISHED
ⓘ
chromatic polynomial ⓘ flow polynomial ⓘ reliability polynomial NERFINISHED ⓘ |
| hasSpecialization |
Potts model partition function
NERFINISHED
ⓘ
all-terminal reliability polynomial ⓘ chromatic polynomial at (1-q,0) ⓘ flow polynomial at (0,1-q) ⓘ number of connected spanning subgraphs ⓘ number of forests ⓘ number of spanning trees ⓘ |
| hasSymmetry | duality relation for planar graphs ⓘ |
| hasVariable |
x
ⓘ
y ⓘ |
| isBivariate | true ⓘ |
| isDefinedFor |
finite graphs
ⓘ
matroids ⓘ |
| isExtensionOf | rank generating function of a matroid ⓘ |
| isInvariantUnder |
graph isomorphism
ⓘ
matroid isomorphism ⓘ |
| namedAfter | W. T. Tutte NERFINISHED ⓘ |
| relatedTo |
Fortuin–Kasteleyn representation
NERFINISHED
ⓘ
Potts model in statistical mechanics ⓘ |
| satisfies |
deletion–contraction recurrence
ⓘ
duality T_G(x,y)=T_{G*}(y,x) for planar dual G* ⓘ |
| usedIn |
knot theory
ⓘ
network reliability ⓘ statistical physics ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.