On Symmetry of Independence Polynomials

Details On Symmetry of Independence Polynomials On Symmetry of Independence Polynomials

2011-05-11

arxiv.org/abs/1105.2202v1

Computer Science

Discrete Mathematics

16 pages, 13 figures

Scientific paper

An independent set in a graph is a set of pairwise non-adjacent vertices, and alpha(G) is the size of a maximum independent set in the graph G. A matching is a set of non-incident edges, while mu(G) is the cardinality of a maximum matching. If s_{k} is the number of independent sets of cardinality k in G, then I(G;x)=s_{0}+s_{1}x+s_{2}x^{2}+...+s_{\alpha(G)}x^{\alpha(G)} is called the independence polynomial of G (Gutman and Harary, 1983). If $s_{j}=s_{\alpha-j}$, 0=< j =< alpha(G), 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 (Stevanovic, 1998). In this paper we show that for every graph G and for each non-negative integer k =< mu(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).

Affiliated with

Also associated with

No associations

Rating

On Symmetry of Independence Polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Symmetry of Independence Polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Symmetry of Independence Polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-611719