A Matrix Criterion for Harmonic Morphisms of Graphs with Applications to Graph Products

Urakawa, and later Baker and Norine, developed the notion of a harmonic morphism as a type of graph morphism with similar properties to holomorphic maps of Riemann surfaces. We give a matrix criterion for harmonic graph morphisms which allows us to translate combinatorial questions about harmonic morphisms to linear algebra questions. We illustrate its use by finding conditions under which certain maps of NEPS graph products (for example, tensor, Cartesian, and strong products) are harmonic, and calculating their vertical and horizontal multiplicity matrices and degrees. We also apply the matrix criterion to lexicographic products, the special case of graph blow-ups, and graph joins.