TY - JOUR

T1 - On symmetry of independence polynomials

AU - Levit, Vadim E.

AU - Mandrescu, Eugen

PY - 2011/9

Y1 - 2011/9

N2 - 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).

AB - 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).

KW - Independence polynomial

KW - Independent set

KW - Palindromic polynomial

KW - Symmetric polynomial

UR - http://www.scopus.com/inward/record.url?scp=84860556027&partnerID=8YFLogxK

U2 - 10.3390/sym3030472

DO - 10.3390/sym3030472

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:84860556027

SN - 2073-8994

VL - 3

SP - 472

EP - 486

JO - Symmetry

JF - Symmetry

IS - 3

ER -