Read More
Date: 28-7-2016
1493
Date: 1-4-2022
1662
Date: 24-3-2022
1527
|
Let be an undirected graph, and let denote the cardinal number of the set of externally active edges of a spanning tree of , denote the cardinal number of the set of internally active edges of , and the number of spanning trees of whose internal activity is and external activity is . Then the Tutte polynomial, also known as the dichromate or Tutte-Whitney polynomial, is defined by
(1) |
(Biggs 1993, p. 100).
An equivalent definition is given by
(2) |
where the sum is taken over all subsets of the edge set of a graph , is the number of connected components of the subgraph on vertices induced by , is the vertex count of , and is the number of connected components of .
Several analogs of the Tutte polynomial have been considered for directed graphs, including the cover polynomial (Chung and Graham 1995), Gordon-Traldi polynomials (Gordon and Traldi 1993), and three-variable -polynomial (Awan and Bernardi 2016; Chow 2016). However, with the exceptions of the the Gordon-Traldi polynomial and -polynomial, these are not proper generalizations of the Tutte polynomial since they are not equivalent to the Tutte polynomial for the special case of undirected graphs (Awan and Bernardi 2016).
The Tutte polynomial can be computed in the Wolfram Language using TuttePolynomial[g, x, y].
The Tutte polynomial is multiplicative over disjoint unions.
For an undirected graph on vertices with connected components, the Tutte polynomial is given by
(3) |
where is the rank polynomial (generalizing Biggs 1993, p. 101). The Tutte polynomial is therefore a rather general two-variable graph polynomial from which a number of other important one- and two-variable polynomials can be computed.
For not-necessarily connected graphs, the Tutte polynomial is related the chromatic polynomial , flow polynomial , rank polynomial , and reliability polynomial by
(4) |
|||
(5) |
|||
(6) |
|||
(7) |
where is the number of vertices in the graph, is the number of edges, and is the number of connected components.
The Tutte polynomial of the dual graph of a graph is given by
(8) |
i.e., by swapping the variables of the Tutte polynomial of the original graph. A special case of this identity relates the flow polynomial of a planar graph to the chromatic polynomial of its dual graph by
(9) |
The Tutte polynomial of a connected graph is also completely defined by the following two properties (Biggs 1993, p. 103):
1. If is an edge of which is neither a loop nor an isthmus, then .
2. If is formed from a tree with edges by adding loops, then
Closed forms for some special classes of graphs are summarized in the following table, where and . The Tutte polynomial of the web graph was considered by Biggs et al. (1972) and Brennan et al. (2013).
graph | |
book graph | |
centipede graph | |
cycle graph | |
empty graph | 1 |
forest | |
gear graph | |
helm graph | |
ladder graph | |
ladder rung graph | |
pan graph | |
path graph | |
star graph | |
sunlet graph | |
wheel graph |
The following table summarizes the recurrence relations for Tutte polynomials for some simple classes of graphs.
graph | order | recurrence |
antiprism graph | 6 | |
book graph | 2 | |
centipede graph | 1 | |
cycle graph | 2 | |
gear graph | 3 | |
helm graph | 3 | |
ladder graph | 2 | |
ladder rung graph | 1 | |
Möbius ladder | 6 | |
pan graph | 2 | |
path graph | 1 | |
prism graph | 6 | |
star graph | 1 | |
sunlet graph | 2 | |
web graph | 6 | |
wheel graph | 3 |
An equation for the Tutte polynomial of the complete graph was found by Tutte (1954, 1967). In particular, has exponential generating function
(10) |
(Gessel 1995, Gessel and Sagan 1996). This can be written more simply in terms of the coboundary polynomial
(11) |
where is the connected component count and is the vertex count of a graph (Martin and Reiner 2005). In this form, the exponential generating function of is given by
(12) |
which can be converted to the corresponding Tutte polynomial using the above relationship and the substitution and . The formula was rediscovered by Pak in the form of the following recurrence
(13) |
where .
A formula for the Tutte polynomial of a complete bipartite graph is given in terms of an bivariate exponential generating function for the coboundary polynomial as
(14) |
by Martin and Reiner (2005).
Nonisomorphic graphs do not necessarily have distinct Tutte polynomials. de Mier and Noy (2004) call a graph that is determined by its Tutte polynomial a -unique graph and showed that wheel graphs, ladder graphs, Möbius ladders, complete multipartite graphs (with the exception of ), and hypercube graphs are -unique graphs. Kuhl (2008) showed that the generalized Petersen graphs and their line graphs are -unique.
The numbers of simple graphs on , 2, ... nodes that are not Tutte-unique for a given value of are 0, 0, 0, 4, 15, 84, 548, 5629, ... (OEIS A243048), while the corresponding numbers of Tutte-unique graphs are 1, 2, 4, 7, 19, 72, 496, 6717, ... (OEIS A243049). The following table summarizes some small co-Tutte graphs.
Tutte polynomial | graphs | |
4 | , ladder rung graph | |
4 | claw graph , path graph | |
5 | , | |
5 | , , | |
5 | fork graph, path graph , star graph | |
5 | paw graph , | |
5 | bull graph, cricket graph, -tadpole graph | |
5 | dart graph, kite graph |
Andrzejak, A. "Splitting Formulas for Tutte Polynomials." J. Combin. Th., Ser. B. 70, 346-366, 1997.
Andrzejak, A. "An Algorithm for the Tutte Polynomials of Graphs of Bounded Treewidth." Disc. Math. 190, 39-54, 1998.
Biggs, N. L. "The Tutte Polynomial." Ch. 13 in Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 97-105, 1993.
Biggs, N. L.; Damerell, R. M.; and Sands, D. A. "Recursive Families of Graphs." J. Combin. Theory Ser. B 12, 123-131, 1972.
Björklund, A.; Husfeldt, T.; Kaski, P.; and Koivisto, M. "Computing the Tutte Polynomial in Vertex-Exponential Time." In Proceedings of the IEEE Symposium on the Foundations of Computer Science (FOCS), 677-686, 2008.
Brennan, C.; Mansour, T.; and Mphako-Banda, E. "Tutte Polynomials of Wheels Via Generating Functions." Bull. Iranian Math. Soc. 39, 881-891, 2013.
Brylawski, T. and Oxley, J. "The Tutte Polynomial and Its Applications." Ch. 6 in Matroid Applications (Ed. N. White). Cambridge, England: Cambridge University Press, pp. 123-225, 1992.
Chow, T Y. "Digraph Analogues of the Tutte Polynomials." Preprint chapter for The CRC Handbook on the Tutte Polynomial and Related Topics (Ed. I. Moffat and J. Ellis-Monaghan). 2016.
Chung, F. R. K. and Graham, R. L. "On the Cover Polynomial of a Digraph." J. Combin. Theory, Ser. B 65, 273-290, 1995.
de Mier, A. and Noy, M. "On Graphs Determined by Their Tutte Polynomial." Graphs Combin. 20, 105-119, 2004.
de Mier, A. and Noy, M. "Tutte Uniqueness of Line Graphs." Disc. Math. 301, 57-65, 2005.
Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications I: The Tutte Polynomial." 28 Jun 2008. http://arxiv.org/abs/0803.3079.
Ellis-Monaghan, J. A. and Merino, C. "Graph Polynomials and Their Applications II: Interrelations and Interpretations." 28 Jun 2008. http://arxiv.org/abs/0806.4699.
Gessel, I. M. "Enumerative Applications of a Decomposition for Graphs and Digraphs." Disc. Math. 139, 257-271, 1995.
Gessel, I. M. and Sagan, B. E. "The Tutte Polynomial of a Graph, Depth-First Search, and Simplicial Complex Partitions." Electronic J. Combinatorics 3, No. 2, R9, 1-36, 1996. http://www.combinatorics.org/Volume_3/Abstracts/v3i2r9.html.
Gordon, G. and Traldi, L. "Polynomials for Directed Graphs." Congr. Numer. 94, 187-201, 1993.
Haggard, G.; Pearce, D. J.; and Royle, G. "Computing Tutte Polynomials" ACM Trans. Math. Software 37, Art. 24, 17 pp., 2010.
Jaeger, F. "Tutte Polynomials and Link Polynomials." Proc. Amer. Math. Soc. 103, 647-665, 1988.
Jaeger, F.; Vertigan, D.; and Welsh, D. "On the Computational Complexity of the Jones and Tutte Polynomials." Math. Proc. Camb. Phil. Soc. 108, 35-53, 1990.
Kuhl, J. S. "The Tutte Polynomial and the Generalized Petersen Graph." Australas. J. Combin. 40, 87-97, 2008.
Pak, I. "Computation of Tutte Polynomials of Complete Graphs." http://www.math.ucla.edu/~pak/papers/Pak_Computation_Tutte_polynomial_complete_graphs.pdf.Martin, J. and Reiner, V. "Cyclotomic and Simplicial Matroids." Israel J. Math. 150, 229-240, 2005.
Sloane, N. J. A. Sequences A243048 and A243049 in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. "A Contribution to the Theory of Chromatic Polynomials." Canad. J. Math. 6, 80-91, 1954.
Tutte, W. T. "On Dichromatic Polynomials." J. Combin. Th. 2, 301-320, 1967.
|
|
مخاطر عدم علاج ارتفاع ضغط الدم
|
|
|
|
|
اختراق جديد في علاج سرطان البروستات العدواني
|
|
|
|
|
مدرسة دار العلم.. صرح علميّ متميز في كربلاء لنشر علوم أهل البيت (عليهم السلام)
|
|
|