A Peek Behind the Curtain

One feature of my forthcoming book with Caroline Melles, Exploring Graphs via Harmonic Morphisms, is its computational emphasis. Many of the examples and insights emerged not from pure contemplation, but from extensive experimentation using SageMath. This post gives a glimpse into the algorithmic machinery that made this exploration possible.

The fundamental problem I faced in generating examples was this: given two graphs Γ₁ and Γ₂, find all harmonic morphisms φ: Γ₂ → Γ₁. This approach is direct—a brute force algorithm that constructs all possible “color lists” (vertex labelings that encode potential morphisms) and tests each one for the harmonic property. Straightforward? Yes. Fast? Definitely not.

However, when the target graph Γ₁ is a path graph, one can do better. The “shell algorithm” exploits the geometry of distance in the source graph. Starting from a chosen vertex v₀, one builds outward through successive neighborhoods—vertices at distance 1, then 2, and so on—assigning colors constrained by distance from the starting point. At each stage, one checks necessary conditions before proceeding, pruning impossible branches early. The automorphism groups of both graphs then generate equivalent colorings, and after removing duplicates, one has a complete enumeration of the harmonic morphisms.

That’s what was done for various choices of small graphs, printing computational data to a file whose name used notation or terminology for the graphs and . Months of computer searches resulted in a number of conjectures that were used to shape the material in the book.