0
EN
1
المرجع الالكتروني للمعلوماتية

الرياضيات

تاريخ الرياضيات

الاعداد و نظريتها

تاريخ التحليل

تار يخ الجبر

الهندسة و التبلوجي

الرياضيات في الحضارات المختلفة

العربية

اليونانية

البابلية

الصينية

المايا

المصرية

الهندية

الرياضيات المتقطعة

المنطق

اسس الرياضيات

فلسفة الرياضيات

مواضيع عامة في المنطق

الجبر

الجبر الخطي

الجبر المجرد

الجبر البولياني

مواضيع عامة في الجبر

الضبابية

نظرية المجموعات

نظرية الزمر

نظرية الحلقات والحقول

نظرية الاعداد

نظرية الفئات

حساب المتجهات

المتتاليات-المتسلسلات

المصفوفات و نظريتها

المثلثات

الهندسة

الهندسة المستوية

الهندسة غير المستوية

مواضيع عامة في الهندسة

التفاضل و التكامل

المعادلات التفاضلية و التكاملية

معادلات تفاضلية

معادلات تكاملية

مواضيع عامة في المعادلات

التحليل

التحليل العددي

التحليل العقدي

التحليل الدالي

مواضيع عامة في التحليل

التحليل الحقيقي

التبلوجيا

نظرية الالعاب

الاحتمالات و الاحصاء

نظرية التحكم

بحوث العمليات

نظرية الكم

الشفرات

الرياضيات التطبيقية

نظريات ومبرهنات

علماء الرياضيات

500AD

500-1499

1000to1499

1500to1599

1600to1649

1650to1699

1700to1749

1750to1779

1780to1799

1800to1819

1820to1829

1830to1839

1840to1849

1850to1859

1860to1864

1865to1869

1870to1874

1875to1879

1880to1884

1885to1889

1890to1894

1895to1899

1900to1904

1905to1909

1910to1914

1915to1919

1920to1924

1925to1929

1930to1939

1940to the present

علماء الرياضيات

الرياضيات في العلوم الاخرى

بحوث و اطاريح جامعية

هل تعلم

طرائق التدريس

الرياضيات العامة

نظرية البيان

قم بتسجيل الدخول اولاً لكي يتسنى لك الاعجاب والتعليق.

Tutte Polynomial

المؤلف:  Andrzejak, A

المصدر:  "Splitting Formulas for Tutte Polynomials." J. Combin. Th., Ser. B. 70

الجزء والصفحة:  ...

20-4-2022

2662

+

-

20

Tutte Polynomial

Let G be an undirected graph, and let i denote the cardinal number of the set of externally active edges of a spanning tree T of G, j denote the cardinal number of the set of internally active edges of T, and t_(ij) the number of spanning trees of G whose internal activity is i and external activity is j. Then the Tutte polynomial, also known as the dichromate or Tutte-Whitney polynomial, is defined by

T(x,y)=sumt_(ij)x^iy^j

(1)

(Biggs 1993, p. 100).

An equivalent definition is given by

T(x,y)=sum(x-1)^(k_A-k)(y-1)^(k_A+n_A-n),

(2)

where the sum is taken over all subsets A of the edge set of a graph G, k_A is the number of connected components of the subgraph on n_A vertices induced by A, n is the vertex count of G, and k is the number of connected components of G.

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 B-polynomial (Awan and Bernardi 2016; Chow 2016). However, with the exceptions of the the Gordon-Traldi polynomial f_8 and B-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, <span style={" src="https://mathworld.wolfram.com/images/equations/TuttePolynomial/Inline23.svg" style="height:22px; width:6px" />x, y<span style=}" src="https://mathworld.wolfram.com/images/equations/TuttePolynomial/Inline24.svg" style="height:22px; width:6px" />].

The Tutte polynomial is multiplicative over disjoint unions.

For an undirected graph on n vertices with c connected components, the Tutte polynomial is given by

T(x+1,y+1)=x^(n-c)R(x^(-1),y)

(3)

where R(x,y) 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 T(x,y) is related the chromatic polynomial pi(x), flow polynomial C^*(u), rank polynomial R(x,y), and reliability polynomial C(p) by

pi(x) = (-1)^(n-c)x^cT(1-x,0)

(4)
C^*(u) = (-1)^(m-n+c)T(0,1-u)

(5)
R(x,y) = x^(n-c)T(x^(-1)+1,y+1)

(6)
C(p) = (1-p)^(n-c)p^(m-n+c)T(1,p^(-1)),

(7)

where n is the number of vertices in the graph, m is the number of edges, and c is the number of connected components.

The Tutte polynomial of the dual graph G^* of a graph G is given by

T_(G^*)(x,y)=T_G(y,x),

(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 C_G^*(u) of a planar graph G to the chromatic polynomial of its dual graph G^* by

C_G^*(u)=u^(-1)pi_(G^*)(u).

(9)

The Tutte polynomial of a connected graph G is also completely defined by the following two properties (Biggs 1993, p. 103):

1. If e is an edge of G which is neither a loop nor an isthmus, then T_G(x,y)=T(G^((e));x,y)+T(G_((e));x,y).

2. If Lambda_(ij) is formed from a tree with i edges by adding j loops, then T(Lambda_(ij);x,y)=x^iy^j

Closed forms for some special classes of graphs are summarized in the following table, where s=sqrt((1+x+x^2+y)^2-4x^2y) and t=sqrt((x+y+1)^2-4xy). The Tutte polynomial of the web graph was considered by Biggs et al. (1972) and Brennan et al. (2013).

graph T(x,y)
book graph S_(n+1) square P_2 ((1+x+x^2)^n[x(y-1)-y]+y(x+x^2+y)^n)/(y-1)
centipede graph x^(2n-1)
cycle graph C_n (x^n-x)/(x-1)+y
empty graph K^__n 1
forest x^(|E|)
gear graph 2^(-n)(-2^n-2^nx-2^ny+2^nxy+(1+x+x^2+y-s)^n+(1+x+x^2+y+s)^n
helm graph x^n<span style={-1-x-y+xy+2^(-n)[(1-t+x+y)^n+(1+t+x+y)^n]}" src="https://mathworld.wolfram.com/images/equations/TuttePolynomial/Inline72.svg" style="height:22px; width:470px" />
ladder graph ((s(x-1)+x^3-xy+y+1)(s+x^2+x+y+1)^n-(-sx+s+x^3-xy+y+1)(-s+x^2+x+y+1)^n)/(2^(n+1)sx^2)
ladder rung graph x^n
pan graph (x[x^n+x(y-1)-y])/(x-1)
path graph P_n x^(n-1)
star graph S_n x^(n-1)
sunlet graph C_n circledot K_1 (x^(2n)+x^n(x(-1+y)-y))/(x-1)
wheel graph W_n xy-x-y-1+2^(1-n)[(x+y+1+t)^(n-1)+(x+y+1-t)^(n-1)]

The following table summarizes the recurrence relations for Tutte polynomials for some simple classes of graphs.

graph order recurrence
antiprism graph 6  
book graph S_(n+1)P_2 2 p_n=(2x^2+2x+y+1)p_(n-1)-(x^2+x+1)(x^2+x+y)p_(n-2)
centipede graph 1 p_n=x^2p_(n-1)
cycle graph C_n 2 p_n=(x+1)p_(n-1)-xp_(n-2)
gear graph 3 p_n=(x^2+x+y+2)p_(n-1)+(-x^2y-x^2-x-y-1)p_(n-2)+x^2yp_(n-3)
helm graph 3 p_n=x(x+y-2)p_(n-1)-x^2(x+1)(y+1)p_(n-2)+x^4p_(n-3)
ladder graph 2 p_n=(x^2+x+y+1)p_(n-1)-x^2yp_(n-2)
ladder rung graph 1 p_n=xp_(n-1)
Möbius ladder M_n 6  
pan graph 2 p_n=(x+1)p_(n-1)-xp_(n-2)
path graph 1 p_n=xp_(n-1)
prism graph Y_n 6  
star graph S_n 1 p_n=xp_(n-1)
sunlet graph C_n circledot K_1 2 p_n=x(x+1)p_(n-1)-x^3p_(n-2)
web graph 6  
wheel graph W_n 3 p_n=(x+y+2)p_(n-1)-(x+1)(y+1)p_(n-2)+xyp_(n-3)

An equation for the Tutte polynomial T_(K_n)(x,y) of the complete graph K_n was found by Tutte (1954, 1967). In particular, T_(K_n)(x,y) has exponential generating function

sum_(n=1)^inftyT_(K_n)(x,y)(u^n)/(n!)=1/(x-1)<span style={[sum_(n=0)^inftyy^((n; 2))(y-1)^(-n)(u^n)/(n!)]^((x-1)(y-1))-1}, " src="https://mathworld.wolfram.com/images/equations/TuttePolynomial/NumberedEquation6.svg" style="height:58px; width:423px" />

(10)

(Gessel 1995, Gessel and Sagan 1996). This can be written more simply in terms of the coboundary polynomial

chi^__G(q,t)=(t-1)^(n_G-c_G)T_G((q+t-1)/(t-1),t),

(11)

where c_G is the connected component count and n_G is the vertex count of a graph G (Martin and Reiner 2005). In this form, the exponential generating function of K_n is given by

1+qsum_(n=1)^inftychi^__(K_n)(q,t)(x^n)/(n!)=(sum_(n=0)^inftyt^((n; 2))(x^n)/(n!))^q,

(12)

which can be converted to the corresponding Tutte polynomial using the above relationship and the substitution q->(x-1)(y-1) and t->y. The formula was rediscovered by Pak in the form of the following recurrence

F_n(x,y)=sum_(k=1)^n(n-1; k-1)(x+y+y^2+...+y^(k-1))F_(k-1)(1,y)F_(n-k)(x,y),

(13)

where F_n(x,y)=T_(K_(n+1))(x,y).

A formula for the Tutte polynomial of a complete bipartite graph K_(m,n) is given in terms of an bivariate exponential generating function for the coboundary polynomial as

1+qsum_(m=0)^inftysum_(n=0)^inftychi^__(K_(m,n))(q,t)(x^my^m)/(m!n!)=(sum_(k=0)^inftysum_(l=0)^inftyt^(kl)(x^ky^l)/(k!l!))^q

(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 T-unique graph and showed that wheel graphs, ladder graphs, Möbius ladders, complete multipartite graphs (with the exception of T_(1,p)), and hypercube graphs are T-unique graphs. Kuhl (2008) showed that the generalized Petersen graphs GP(m,2) and their line graphs L(GP(m,2)) are T-unique.

The numbers of simple graphs on n=1, 2, ... nodes that are not Tutte-unique for a given value of n 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.

n Tutte polynomial graphs
4 x^2 P_3 union K_1, ladder rung graph 2P_2
4 x^3 claw graph K_(1,3), path graph P_4
5 x^2 P_3 union 2K_1, 2P_2 union K_1
5 x^3 K_(1,3) union K_1, P_3 union P_2, P_4 union P_1
5 x^4 fork graph, path graph P_5, star graph S_5
5 x(x+x^2+y) paw graph  union K_1, C_3 union P_2
5 x^2(x+x^2+y) bull graph, cricket graph, (3,2)-tadpole graph
5 x(x+2x^2+x^3+y+2xy+y^2) dart graph, kite graph

REFERENCES

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.

الاكثر قراءة في نظرية البيان

اخر الاخبار

اخبار العتبة العباسية المقدسة

مضيف العتبة العباسية المقدسة يقيم مجلس عزائه السنوي لإحياء ذكرى عاشوراء

قسم الشؤون الفكرية ينجز المراحل النهائية لمشروع الأرشفة الرقمية في كلية العلوم بجامعة البصرة

بعد إدامتها.. قسم صناعة الشبابيك ينهي تركيب الأعمدة الوسطية لأبواب حرم مرقد أبي الفضل العباس (عليه السلام)

في اليوم السابع من المحرم.. العتبة العباسية المقدسة تستذكر سيرة أبي الفضل العباس (عليه السلام)

المزيد
الآخبار الصحية

كيف يختبئ فيروس "إيبولا" داخل الجسم؟..دراسة تكشف السر الخطير

أسرار البطيخ الأحمر.. فوائد صحية تتجاوز مجرد الترطيب

ليس عدد الساعات فقط.. توقيت النوم يحمي قلبك ومزاجك

القهوة قبل الإفطار أم بعده.. أيهما أفضل لصحتك؟

المزيد
الآخبار التكنلوجية

الإمارات تطلق "زايد".. متحدث رقمي مدعوم بالذكاء الاصطناعي

لحفظ أسرار البشرية.. بدء بناء "الصندوق الأسود" للأرض

نماذج الذكاء الاصطناعي تفشل في تجاوز خبراء الرياضيات في اختبار بحثي معقد

ابتكار أول كاشف كمي للمادة المظلمة

المزيد

اشترك بقناتنا على التلجرام ليصلك كل ما هو جديد

EN