The independence polynomial of a graph - a survey

Abstract

A stable (or independent) set in a graph is a set of pairwise non-adjacent vertices. The stability number α(G) is the size of a maximum stable set in the graph G. There are three different kinds of structures that one can see observing behavior of stable sets of a graph: the enumerative structure, the intersection structure, and the exchange structure. The independence polynomial of G I(G; x) = α(G) � k=0 skx k = s0 + s1x + s2x 2 +... + sα(G)x α(G), defined by Gutman and Harary (1983), is a good representative of the enumerative structure (sk is the number of stable sets of cardinality k in a graph G). One of the most general approaches to graph polynomials was proposed by Farrell (1979) in his theory of F-polynomials of a graph. According to Farrell, any such polynomial corresponds to a strictly prescribed family of connected subgraphs of the respective graph. For the matching polynomial of a graph G, this family consists of all the edges of G, for the independence polynomial of G, this family includes all the stable sets of G. In fact, various aspects of combinatorial information concerning a graph is stored in the coefficients of a specific graph polynomial. In this paper, we survey the most important results referring the independence polynomial of a graph.