Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872659 | Discrete Applied Mathematics | 2012 | 7 Pages |
Abstract
An independent set of a graph G is a set of pairwise non-adjacent vertices. G is well-covered if all its maximal independent sets have the same size, denoted by α(G). Let fs(G) for 0â¤sâ¤Î±(G) denote the number of independent sets of s vertices in G. The independence polynomial I(G;x)=âi=0α(G)fs(G)xs defined first by Gutman and Harary has been the focus of considerable research recently. Motivated by a result of Gutman for some compound graphs, we extend the result for more general compound graphs. In particular, we use our main results to determine the coefficients fs(G) for some well-covered graphs and present the exact independence polynomials of several well-covered graphs. Using the independence polynomials we derive some interesting combinatorial identities and give exact values of the Merrifield-Simmons index for some special classes of graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Lanzhen Song, William Staton, Bing Wei,