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

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

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

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

هل تعلم

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

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

نظرية البيان

الرياضيات : نظرية البيان :

Independence Polynomial

المؤلف:  Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M.

المصدر:  "Domination and Irredundance in the Queens Graph." Disc. Math. 163

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

19-4-2022

1588

Independence Polynomial

Let s_k be the number of independent vertex sets of cardinality k in a graph G. The polynomial

I(x)=sum_(k=0)^(alpha(G))s_kx^k,

(1)

where alpha(G) is the independence number, is called the independence polynomial of G (Gutman and Harary 1983, Levit and Mandrescu 2005). It is also goes by several other names, including the independent set polynomial (Hoede and Li 1994) or stable set polynomial (Chudnovsky and Seymour 2004).

The independence polynomial is closely related to the matching polynomial. In particular, since independent edge sets in the line graph L(G) correspond to independent vertex sets in the original graph G, the matching-generating polynomial of a graph G is equal to the independence polynomial of the line graph of G (Levit and Mandrescu 2005):

mu_G(x)=I_(L(G))(x).

(2)

The independence polynomial is also related to the clique polynomial C_G(x) by

C_G(x)=I_(G^_)(x),

(3)

where G^_ denotes the graph complement (Hoede and Li 1994), and to the vertex cover polynomial by

I_G(x)=x^nPsi_g(x^(-1)),

(4)

where n=|G| is the vertex count of G (Akban and Oboudi 2013).

The independence polynomial of a disconnected graph is equal to the product of independence polynomials of its connected components.

Precomputed independence polynomials for many named graphs in terms of a variable x can be obtained in the Wolfram Language using GraphData[graph, "IndependencePolynomial"][x].

The following table summarizes closed forms for the independence polynomials of some common classes of graphs. Here, s=sqrt(x^2+6x+1), t=sqrt(1+4x), and u=sqrt((x+1)(5x+1)).

graph I(x)
Andrásfai graph A_n 1+(3n-1)x(x+1)^(n-1)
barbell graph [1+(n-1)x][1+(n+1)x]
book graph S_(n+1) square P_2 2x(1+x)^n+(1+2x)^n
centipede graph ((-1+u-3x)(1-u+x)^n+(1+u+x)^n(1+u_3x))/(2^(n+1)u)
cocktail party graph K_(n×2) 1+nx(x+2)
complete bipartite graph K_(n,n) 2(x+1)^n-1
complete graph K_n 1+nx
complete tripartite graph K_(n,n,n) 3(x+1)^n-2
crossed prism graph 2^(-n)[(1+2x(2+x)-sqrt((1+2x)(1+6x)))^n+(1+2x(2+x)+sqrt((1+2x)(1+6x)))^n]
crown graph 2(x+1)^n+nx^2-1
cycle graph C_n 2(-x)^(n/2)T_n(1/(2sqrt(-x)))
gear graph x(x+1)^n+((1-t+2x)^n+(1+t+2x)^n)/(2^n)
helm graph 2^(-n)[2^nx(+x+1)^n+(x-u+1)^n+(x+u+1)^n]
ladder graph 2^(-(n+1))[(s-3x-1)(x-s+1)^n+(s+3x+1)(x+s+1)^n]
ladder rung graph nP_2 (2x+1)^n
Möbius ladder M_n 2^(-n)[-2^n(-x)^n+(x-s+1)^n+(x+s+1)^n]
pan graph ((1-t)^n(-x+t(2+x))+(1+t)^n(x+t(2+x)))/(2^(n+1)t)
path graph P_n x^((n+1)/2)F_(n+2)(x^(-1/2))
prism graph 2^(-n)[2^n(-x)^n+(1+x-s)^n+(1+x+s)^n]
star graph S_n x+(1+x)^(n-1)
sun graph (x+1)^(n-2)[1+x(x+n+2)]
sunlet graph C_n circledot K_1 2^(-n)[(u+x+1)^n+(-u+x+1)^n]
triangular graph 2^(-n/2)(-isqrt(x))^nH_n(i/(sqrt(2x)))
  =2^(n/2)(-1/x)^(-n/2)U(1/2n,1/2,1/(2x))
wheel graph W_n (-(1-t)^n-(1-t)^nt+(t-1)(1+t)^n+2^(n-1)x^2)/(2^(n+1)x)

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

graph order recurrence
Andrásfai graph 3 p_n(x)=(2x+3)p_(n-1)(x)-(x+1)(x+3)p_(n-2)(x)+(x+1)^2p_(n-3)(x)
antiprism graph 3 p_n(x)=x^2p_n-3(x)+2xp_n-2(x)+p_n-1(x)
barbell graph 3 p_n(x)=3p_(n-1)(x)-3p_(n-2)(x)+p_(n-3)(x)
book graph S_(n+1) square P_2 2 p_n(x)=(3x+2)p_(n-1)(x)-(x+1)(2x+1)p_(n-2)(x)
centipede graph 2 p_n(x)=(x+1)p_(n-1)(x)+x(x+1)p_(n-2)(x)
cocktail party graph K_(n×2) 2 p_n(x)=2p_(n-1)(x)-p_(n-2)(x)
complete bipartite graph K_(n,n) 2 p_n(x)=(x+2)p_(n-1)(x)-(x+1)p_(n-2)(x)
crossed prism graph 2 p_n(x)=(2x^2+4x+1)p_(n-1)(x)-x^2(x^2+4x+2)p_(n-2)(x)
crown graph 3 p_n(x)=(x+3)p_(n-1)(x)-(2x+3)p_(n-2)(x)+(x+1)p_(n-3)(x)
cycle graph C_n 2 p_n(x)=p_(n-1)(x)+xp_(n-2)(x)
gear graph 3 p_n(x)=(3x+2)p_(n-1)(x)-(3x^2+3x+1)p_(n-2)(x)+(x+1)x^2p_(n-3)(x)
helm graph 3 p_n(x)=2(x+1)p_(n-1)(x)-(x+1)p_(n-2)(x)-x(x+1)^2p_(n-3)(x)
ladder graph 2 p_n(x)=(x+1)p_(n-1)(x)+xp_(n-2)(x)
ladder rung graph 1 p_n(x)=(2x+1)p_(n-1)(x)
Möbius ladder M_n 3 p_n(x)=p_(n-1)(x)+x(x+2)p_(n-2)(x)+x^2p_(n-3)(x)
pan graph 2 p_n(x)=p_(n-1)(x)+xp_(n-2)(x)
path graph P_n 2 p_n(x)=p_(n-1)(x)+xp_(n-2)(x)
prism graph Y_n 3 p_n(x)=p_(n-1)(x)+x(x+2)p_(n-2)(x)+x^2p_(n-3)(x)
star graph S_n 2 p_n(x)=(x+2)p_(n-1)(x)-(x+1)p_(n-2)(x)
sun graph 2 p_n(x)=2(x+1)p_(n-1)(x)-(x+1)^2p_(n-2)(x)
sunlet graph C_n circledot K_1 2 p_n(x)=(x+1)p_(n-1)(x)+x(x+1)p_(n-2)(x)
web graph 3 p_n(x)=(x+1)p_(n-1)(x)+2x(x+1)^2p_(n-2)(x)+x^2(x+1)^2p_(n-3)(x)
wheel graph W_n 3 p_n(x)=2p_(n-1)(x)+(x-1)p_(n-2)(x)-xp_(n-3)(x)

Nonisomorphic graphs do not necessarily have distinct independence polynomials. The following table summarizes some co-independence graphs.

n independence polynomial graphs
4 (1+x)(1+3x) (4,6), path graph P_4
4 1+4x+2x^2 paw graph, square graph
5 (1+x)^2(1+3x) (5,8), (5,9)
5 (1+x)(1+4x) butterfly graph, house graph, kite graph, (5,24)
5 (1+x)(1+4x+x^2) banner graph, bull graph, (5,15)
5 (1+x)(1+4x+2x^2) fork graph, (5,10), (5,14)
5 1+5x+2x^2 house X graph, wheel graph W_5
5 1+5x+3x^2 gem graph, (5,31), (4,1)-lollipop graph
5 1+5x+5x^2 cycle graph C_5, (3,2)-tadpole graph
5 1+5x+4x^2+x^3 dart graph, complete bipartite graph K_(2,3)

The independence polynomial of a tree is unimodal, and the independence polynomial of a claw-free graph is logarithmically concave.

REFERENCES

Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.

Chudnovsky, M. and Seymour, P. "The Roots of the Stable Set Polynomial of a Claw-Free Graph." 2004. http://www.math.princeton.edu/÷mchudnov/publications.html.

Gutman, I. and Harary, F. "Generalizations of the Matching Polynomial." Utilitas Mathematica 24, 97-106, 1983.

Hoede, C. and Li, X. "Clique Polynomials and Independent Set Polynomials of Graphs." Disc. Math. 125, 219-228, 1994.

Levit, V. E. and Mandrescu, E. "The Independence Polynomial of a Graph--A Survey." In Proceedings of the 1st International Conference on Algebraic Informatics. Held in Thessaloniki, October 20-23, 2005 

(Ed. S. Bozapalidis, A. Kalampakas, and G. Rahonis). Thessaloniki, Greece: Aristotle Univ., pp. 233-254, 2005.

EN

تصفح الموقع بالشكل العمودي