Search

Abstract: The independence polynomial of a graph G is the function , where is the number of independent sets of vertices in G of cardinality k. We investigate here the average independence polynomial, where the average is taken over all independence polynomials of (labeled) graphs of order n. We prove that while almost every independence polynomial has a nonreal root, the average independence polynomials always have all real, simple roots. [Copyright &y& Elsevier]

The k-polynomial of a simplicial complex C is the function kC(x)=∑i⩾1 fixi where fi is the number of i-faces in C. These k-polynomials are closed under composition, and we are lead to ask: for higher composites of a complex C with itself, what happens to the roots of their k-polynomials? We prove that they converge to the Julia set of kC(x), thereby associating with C a fractal. For 2-dimensional complexes we exploit the Mandelbrot set to determine when their fractals are connected, and determine the connectness of the fractals for certain families of ‘stripped’ complexes. [Copyright &y& Elsevier]

Independence polynomials of graphs enjoy the property of essentially being closed under graph composition (or ‘lexicographic product’). We ask here: for higher products of a graph G with itself, where are the roots of their independence polynomials approaching? We prove that in fact they converge (in the Hausdorff topology) to the Julia set of the independence polynomial of G, thereby associating with G a fractal. The question arises as to when these fractals are connected, and for graphs with independence number 2 we exploit the Mandelbro¨t set to answer the question completely. [Copyright &y& Elsevier]