P-Generating Polynomials and the P-Fractal of a Graph

Abstract

We define the P -generating polynomial for a graph G and property P as the generating polynomial for the number of P-subgraphs of G of each size. This polynomial is a generalization of the independence polynomial and so results for the independence polynomial are generalized to hold for properties other than independence. We look at computing the P -generating polynomial of product graphs for certain properties P. We then look at determining the nature and location of the roots of P-generating polynomials in general, showing for which properties the roots are real for all graphs. The roots of the P-generating polynomials of graph products lead to the P-fractal of a graph for all properties P that are closed under graph substitution.