Various Results on Enumerations of Graph Homomorphisms

Doctoral Dissertation


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].


Attribute NameValues
  • etd-08042014-130108

Author Justin Mathew Hilyard
Advisor David Galvin
Contributor David Galvin, Committee Chair
Contributor Hemanshu Kaul, Committee Member
Contributor Sonja Mapes, Committee Member
Contributor Juan Migliore, Committee Member
Degree Level Doctoral Dissertation
Degree Discipline Mathematics
Degree Name Doctor of Philosophy
Defense Date
  • 2014-07-30

Submission Date 2014-08-04
  • United States of America

  • combinatorics

  • independent sets

  • graph homomorphisms

  • independence polynomials

  • graph theory

  • stirling numbers

  • University of Notre Dame

  • English

Record Visibility Public
Embargo Release Date
  • 2015-10-06

Content License
  • All rights reserved

Departments and Units

Digital Object Identifier


This DOI is the best way to cite this doctoral dissertation.


Please Note: You may encounter a delay before a download begins. Large or infrequently accessed files can take several minutes to retrieve from our archival storage system.