Caroline Melles and I have been working for some years on a 2-volume book in graph theory which investigates harmonic morphisms. These are, roughly speaking, mappings from one graph to another that preserve locally harmonic functions on these graphs. Therefore, this topic fits into the general framework of harmonic analysis on graphs.

This post only concerns the first volume. The intent here is to mention some of the types of results we obtain. Of course, by no means is it intended to be a complete description.

The second volume will be summarized in a separate post.

Graphs in our book are unweighted and, unless stated otherwise, have no loops or multiple edges. The basic idea is this: in chapter 2 we classify harmonic morphisms using a criteria expressed as a matrix identity. For various graph-theoretical constructions (such as edge deletion or join or a graph product or …) that can be performed on a given graph Gamma, we pick a graph morphism associated to the construction (such as sending a vertex in the constructed graph to the given graph). That morphism is associated to a matrix (which we called the vertex map matrix in chapter 3 of our earlier book, Adventures in Graph Theory). When this matrix satisfies the above-mentioned matrix criteria then the associated morphism is harmonic.

Chapter 1 is on Graph Morphisms.

This chapter is devoted to background on graph morphisms and some of the methods we use to study them.

1. Roughly speaking, a morphism is a mapping between graphs that preserves incidence structure. After defining horizontal and vertical edges, vertical multiplicities, local horizontal multiplicities, it recalls well-known graph families like cycle graphs, path graphs, and complete graphs.
2. There are a few very useful degree identities. First, there is a fundamental formula relating vertex degrees to multiplicities under morphisms. There is also a formula for the degree
   of the morphism in terms of vertical multiplicities and local horizontal multiplicities.
3. A topic threading through the book is that of matrix-theoretic methods. This first chapter introduces vertex map matrices and edge map matrices that encode morphisms. After establishing key matrix identities and products, reviews adjacency matrices and their spectra, with detailed analysis of cycle graph eigenvalues using Chebyshev polynomials and complex roots of unity.
4. It recalls signed and unsigned incidence matrices, with and without edge orientations, and establishes the fundamental Graph Homomorphism Identity relating incidence matrices to morphism matrices,
5. introduces Laplacian matrices as differences of degree and adjacency matrices, connecting to the incidence matrix framework.
6. Introduced graph blowup morphisms via a blowup construction where vertices are replaced by independent sets, creating natural homomorphisms with specific structural properties.
7. Some functorial properties of graph morphisms are established, such as how morphisms behave under graph constructions like subdivisions, smoothing, deletions, and substitutions.
8. The chapter ends with exercises and a chapter summary.

Chapter 2 on Harmonic Morphisms

This chapter is devoted to the basics of harmonic morphisms.

1. Introduces the core definition: a graph morphism is harmonic if local horizontal multiplicities are constant across edges incident to each vertex’s image.
2. Cycle space and cocycle space – Develops the algebraic framework using homology and cohomology of graphs. Covers Urakawa’s theorem on pullbacks of harmonic 1-forms and Baker-Norin results on divisors and Jacobians.
3. Matrix-theoretic methods – Establishes the fundamental matrix characterization: a morphism is harmonic iff there exists a diagonal multiplicity matrix satisfying specific adjacency matrix identities. Proves equivalence with an analogous Laplacian matrix identity and an analogous incidence matrix criteria.
4. The Riemann-Hurwitz formula – Presents the graph-theoretic analogue relating genera of graphs via harmonic morphisms, with matrix proof and applications to regular graphs.
5. Some functorial consequences – Demonstrates how harmonic morphisms interact with graph constructions like subdivision, edge substitution, leaf addition, and deletion. Shows these
   operations preserve harmonicity under appropriate conditions.
6. The chapter ends with exercises and a chapter summary.

All harmonic morphisms from this graph to C4 are covers.

1. Fundamental Problem: Given a graph Gamma1, for which graphs Gamma2 is there a non-trivial harmonic morphism phi from Gamma2 to Gamma1?

1. Follow-up question: Can the number of such phi be counted?

Chapter 3 on Counting Problems

This chapter looks at various families, such as the path graphs. What is especially remarkable is that, as we will see, the problem of counting harmonic morphisms often boils down to solving certain recurrance relations, some of which arose (in a completely different context of course) in
the work of medieval mathematicians, both in Europe and in India.

1. Regarding harmonic morphisms between path graphs, we show how to construct and count the harmonic morphisms from longer path graphs to shorter ones.
2. Regarding harmonic morphisms between cycle graphs, we show how to construct and count the harmonic morphisms from larger cycle graphs (when they exist) to smaller ones. It turns out all such harmonic morphisms are necessarily covers.
3. Regarding harmonic morphisms between complete graphs, we show how to construct and count the harmonic morphisms from larger complete graphs (when they exist) to smaller ones.
4. Harmonic morphisms to P2 (arising from the Baker-Norin Theorem) can be counted.
5. Harmonic morphisms to P3 (the path graph with only 3 vertices) can be counted in special cases.
   There are lots of open questions, such as which trees have a harmonic morphism to P3.
6. The chapter ends with exercises and a chapter summary.

Chapter 4 on Harmonic Quotient Morphisms

This chapter studies quotient graphs arising from group actions and from vertex partitions.

1. Quotient graphs from group actions. Harmonic actions and transitive actions are studied separately.
2. Quotient graphs from paritions. Orbit partitions and equitable partitions are studied.
3. As a nice application of harmonic morphisms with particularly nice structural properties, we consider multicovers and blowup graphs.
4. The last section provides explicit formulas for the eigenvalue spectra of harmonic blowups of bipartite graphs, connecting the eigenvalues of the source and target graphs through the blowup parameters. The main result is the Godsil-McKay Theorem.
5. The chapter ends with exercises and a chapter summary.

Chapter 5 on Graph Morphisms and Graph Products

This chapter studies graph morphisms associated to tensor products of graphs and lexicographical products of graphs.

Roughly speaking, a graph product of Gamma1 with Gamma2 is a graph Gamma3 = (V3, E3), where V3 = V1 x V2 is the Cartesian product and there is a rule for the edges E3 based on some conditions on the vertices. The graph products considered in this book are the disjunctive, Cartesian, tensor, lexicographic, and the strong products.

The most basic questions one wants answered are these:
is the projection pr1 : Gamma1 x Gamma2 to Gamma1 harmonic, and
is the projection pr2 : Gamma1 x Gamma2 to Gamma2 harmonic?
If they do turn out to be harmonic morphisms, we also want to know the vertical and horizontal multiplicities as well. If they do not turn out to be harmonic morphisms, we also want (if possible) to establish conditions on the graphs under which the projections are harmonic.

However, we want to not only consider products of graphs but also products of morphisms.
In this case, the most basic question one wants answered is this:
Given harmonic morphisms phi : Gamma2 to Gamma1 and phi’ : Gamma2′ to Gamma1′, is the
product phi x phi’ harmonic?

1. For example, we show that projection morphisms from tensor products are always harmonic with explicit horizontal multiplicity formulas.
2. Moreover, we prove that the tensor product of harmonic morphisms (without vertical edges) yields a harmonic morphism with horizontal multiplicity matrix given by the Kronecker product of the original multiplicity matrices.
3. If Gamma x Gamma’ is a lexicographical product then the projection onto the first factor, pr1, is a harmonic morphism. However, the projection onto the second factor is not in general.
4. We establish a connection between the balanced blowup graph and a lexicographical product. One corollary of this connection is that the blowdown graph agrees with the first projection of the product, so is a harmonic morphism.

Chapter 6 on More Products and Constructions

1. This chapter studies graph morphisms associated to Cartesian/strong/disjunctive products of graphs as well as joins and NEPS graphs.
2. For example, we show that projection morphisms from Cartesian products or from strong products are always harmonic with explicit horizontal multiplicity formulas.
3. Roughly speaking, one of the results states:
   Given two m-quasi-multicovers phi from Gamma2 to Gamma1 and phi’ from Gamma2′ to Gamma1′, the Cartesian product phi x phi’ is also an m-quasi-multicover (hence harmonic).
4. Another result, roughly speaking, states:
   Given two harmonic morphisms phi from Gamma2 to Gamma1 and phi’ from Gamma2′ to Gamma1′, the
   strong product phi x phi’ is also harmonic.
5. Can one classify the graphs for which the disjunctive product projections pr1 or pr2 are graph morphisms?
6. For example, we show that if phi from Gamma2 to Gamma1 and phi’ from Gamma2′ to Gamma1′ are graph morphisms, then the associated product map from Gamma2 x Gamma2′ to Gamma1 x Gamma1′ (where x is the disjunctive product) is, in general, not a graph morphism.
7. Given two harmonic morphisms phi from Gamma2 to Gamma1 and phi’ from Gamma2′ to Gamma1′, the join morphism phi wedge phi’ is harmonic if and only if a certain technical condition is true.
8. A theorem due to Urakawa states that projection morphisms from a NEPS graph to one
   of its factors are always harmonic. Moreover, we give explicit horizontal multiplicity formulas.
9. The chapter ends with exercises and a chapter summary.

Computations are supported throughout using SageMath and Mathematica. The plan is the publish the volume with Birkhauser. We thank the editors there, especially John Benedetto, for their encouragement and guidance.