ABSTRACT

A number of classical models in statistical physics, such as the Ising model, Potts model, and lattice gas, can be formulated in terms of the generating function for weighted versions of homo-morphisms from G to some graph H. This chapter discusses the generating polynomial for homomorphisms from a graph G to the most general weighted graph on q vertices. For a fixed q, this is an object of polynomial size which contains a wealth of information about the graph G, but as we will later show it is not a complete graph invariant. The chapter describes this generating function as a polynomial, then recalls the definitions of a number of well-known graph polynomials, and partition functions from physics, and then proceeds to study the properties and relationships of these polynomials. There has been several approaches to defining an analogue of the Tutte polynomial for directed graphs as well.