Various Results on Enumerations of Graph Homomorphisms

Given two graphs G and H, a homomorphism from G to H is a map from the vertices of G to the vertices of H that preserves adjacency. Many graph notions can be described using graph homomorphisms, including independent sets, matchings, and graph colorings. In this dissertation, we consider questions in each of these areas. Wang and Zhu [49] demonstrated the log-concavity of the independence polynomial for a number of infinite recursively-defined graph classes. For the first question that we consider, we extend their method to demonstrate the log-concavity of the independence polynomial for a wider range of such classes, showing, for example, that the (n,2)-centipede and (n,2,k)-star-centipede have log-concave independence polynomials for even n and all k, and we describe a technique that can be applied in the pursuit of results for other similarly-structured graphs. The graphs in question give rise to k-periodic recurrence relations. We present a system for reducing these periodic recurrence relations to ordinary second-order recurrence relations that is more applicable than existing work in the field. There has been much discussion (for example, [52], [26], and [22]), on the following question: for each fixed H, n and d, what is the maximum, over all n-vertex, d-regular G, of hom(G,H), the number of homomorphisms from G to H? While the question has been largely settled for bipartite G, it is still quite open for non-bipartite G. Offering further progress on this question, we next establish conditions on H, in terms of certain linear programming problems, under which we can obtain an upper bound on hom(G;H), valid for all regular G, that is very close to best possible. We then establish a number of infinite families of graphs that satisfy these conditions. Finally, we present a q-weighted enumeration of matchings of complete bipartite graphs, an enumeration which was key to proving the validity of a new combinatorial interpretation of the q-analog of a generalization of the Stirling numbers of the second kind in work with Engbers and Galvin [20].