On symmetry of independence polynomials

Vadim E. Levit, Eugen Mandrescu

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء

5 اقتباسات (Scopus)

ملخص

An independent set in a graph is a set of pairwise non-adjacent vertices, and α(G) is the size of a maximum independent set in the graph G. A matching is a set of non-incident edges, while μ(G) is the cardinality of a maximum matching. If s k is the number of independent sets of size k in G, then I(G; x) = s 0 + s 1x + s 2x 2 + ... + s αx α, α = α (G), is called the independence polynomial of G (Gutman and Harary, 1986). If s j = s α-j for all 0 ≤ j ≤ [α=2], then I(G; x) is called symmetric (or palindromic). It is known that the graph G Ο 2K 1, obtained by joining each vertex of G to two new vertices, has a symmetric independence polynomial (Stevanović, 1998). In this paper we develop a new algebraic technique in order to take care of symmetric independence polynomials. On the one hand, it provides us with alternative proofs for some previously known results. On the other hand, this technique allows to show that for every graph G and for each non-negative integer k ≤ μ (G), one can build a graph H, such that: G is a subgraph of H, I (H; x) is symmetric, and I (G ο 2K 1; x) = (1 + x) k I (H; x).

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)472-486
عدد الصفحات15
دوريةSymmetry
مستوى الصوت3
رقم الإصدار3
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - سبتمبر 2011

بصمة

أدرس بدقة موضوعات البحث “On symmetry of independence polynomials'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا