In the works: a book “Exploring Graphs via Harmonic Morphisms”

Posted on 2025/10/07 by wdjoyner

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.

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.
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.
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.
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,
introduces Laplacian matrices as differences of degree and adjacency matrices, connecting to the incidence matrix framework.
Introduced graph blowup morphisms via a blowup construction where vertices are replaced by independent sets, creating natural homomorphisms with specific structural properties.
Some functorial properties of graph morphisms are established, such as how morphisms behave under graph constructions like subdivisions, smoothing, deletions, and substitutions.
The chapter ends with exercises and a chapter summary.

Chapter 2 on Harmonic Morphisms

This chapter is devoted to the basics of harmonic morphisms.

Introduces the core definition: a graph morphism is harmonic if local horizontal multiplicities are constant across edges incident to each vertex’s image.
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.
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.
The Riemann-Hurwitz formula – Presents the graph-theoretic analogue relating genera of graphs via harmonic morphisms, with matrix proof and applications to regular graphs.
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.
The chapter ends with exercises and a chapter summary.

All harmonic morphisms from this graph to C4 are covers.

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

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.

Regarding harmonic morphisms between path graphs, we show how to construct and count the harmonic morphisms from longer path graphs to shorter ones.
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.
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.
Harmonic morphisms to P2 (arising from the Baker-Norin Theorem) can be counted.
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.
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.

Quotient graphs from group actions. Harmonic actions and transitive actions are studied separately.
Quotient graphs from paritions. Orbit partitions and equitable partitions are studied.
As a nice application of harmonic morphisms with particularly nice structural properties, we consider multicovers and blowup graphs.
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.
The chapter ends with exercises and a chapter summary.

Chapter 5 on Graph Morphisms and Graph Products

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?

For example, we show that projection morphisms from tensor products are always harmonic with explicit horizontal multiplicity formulas.
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.
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.
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

This chapter studies graph morphisms associated to Cartesian/strong/disjunctive products of graphs as well as joins and NEPS graphs.
For example, we show that projection morphisms from Cartesian products or from strong products are always harmonic with explicit horizontal multiplicity formulas.
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).
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.
Can one classify the graphs for which the disjunctive product projections pr1 or pr2 are graph morphisms?
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.
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.
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.
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.

The Beautiful Math of Tangent Lines: Unveiling the Lemniscate’s Secrets

Posted on 2025/01/16 by wdjoyner

An experimental post

I asked Gemini to create a blog post based on this plot (below) and the Python code I wrote (based on ideas explained to me by Edray Goins) that generated it. (The prompt I fed to Gemini was modified from a prompt found online for generating a blog post about food.) The response, basically unedited, is below. The topic is inspired by the PhD thesis of Euphemia Haynes (a student of Aubrey Landry, Catholic University of America, 1943). See this earlier post for more information on it.

Mathematics can be beautiful, and sometimes that beauty is hidden in plain sight. Take, for instance, this striking image:

a graceful lemniscate curve adorned with a web of tangent lines, all seemingly converging on a single point. This isn’t some artistic rendering; it’s the output of a fascinating algorithm, written in Python and SageMath, plot_lemniscate_quartic_tangents.

This algorithm doesn’t just draw a pretty picture; it solves a sophisticated geometric problem: finding all the tangent lines to a lemniscate quartic that also pass through a specific point on the curve. Let’s dissect the magic:

The Lemniscate: The algorithm begins by defining the lemniscate quartic curve. This curve, shaped like a sideways figure-eight, has a unique and elegant equation: (x² + y²)² = a(x² – y²), where ‘a’ is a constant.
The Target Point: We choose a specific point, P0, on the lemniscate. This is the point where all our tangent lines will magically meet.
The Tangent Hunt: This is where the algorithm gets clever. It doesn’t directly solve for the tangent lines. Instead, it cleverly iterates through numerous points (P) on the lemniscate. For each point, it calculates two things:
- The slope of the secant line connecting P0 and P.
- The slope of the tangent line to the lemniscate at point P.
The Convergence: If the slopes from step 3 are approximately equal (within a tolerance), it means the secant line through P0 and P is also a tangent line to the curve at P. This line is added to our collection of tangent lines.
The Reveal: Finally, the algorithm plots the lemniscate along with all the tangent lines it discovered. The result is the captivating image we see—a testament to the hidden geometric relationships within this seemingly simple curve.

The algorithm isn’t just about finding tangents; it reveals a beautiful correspondence between points on the lemniscate and its tangent lines. It’s a visual exploration of the intricate geometry underlying algebraic curves, demonstrating how computation can unveil hidden mathematical beauty. So next time you see a seemingly simple curve, remember the rich and sometimes surprising geometry hiding within.

Harmonic quotients of regular graphs – examples

Posted on 2023/01/06 by wdjoyner

Caroline Melles and I have written a preprint that collects numerous examples of harmonic quotient morphisms $\phi : \Gamma_2 \to \Gamma_1$ , where $\Gamma_1=\Gamma_2/G$ is a quotient graph obtained from some subgroup $G \subset Aut(\Gamma_2)$ . The examples are for graphs having a small number of vertices (no more than 12). For the most part, we also focused on regular graphs with small degree (no more than 5). They were all computed using SageMath and a module of special purpose Python functions I’ve written (available on request). I’ve not counted, but the number of examples is relatively large, maybe over one hundred.

I’ll post it to the math arxiv at some point but if you are interested now, here’s a copy: click here for pdf.

A graph_id function in SageMath

Posted on 2022/09/07 by wdjoyner

While GAP has a group_id function which locates a “small” group in a small groups database (see the SageMath page or the GAP page for more info), AFAIK, SageMath doesn’t have something similar. I’ve written one (see below) based on the mountain of hard work done years ago by Emily Kirkman.

def graph_id_graph6(Gamma, verbose=False):
    """
    Returns the graph6 id of Gamma = (V,E).
    If verbose then it also displays the table of all graphs with
    |V| vertices and |E| edges.

    Assumes Gamma is a "small" graph.

    EXAMPLES:
    sage: Gamma = graphs.HouseGraph()
    sage: graph_id_graph6(Gamma, verbose=False)
    'Dbk'
    sage: graph_id_graph6(Gamma, verbose=True)

     graphs with 5 vertices and 6 edges:

    Graph6               Aut Grp Size         Degree Sequence     
    ------------------------------------------------------------
    DB{                  2                    [1, 2, 2, 3, 4]     
    DFw                  12                   [2, 2, 2, 3, 3]     
    DJ[                  24                   [0, 3, 3, 3, 3]     
    DJk                  2                    [1, 2, 3, 3, 3]     
    DK{                  8                    [2, 2, 2, 2, 4]     
    Dbk                  2                    [2, 2, 2, 3, 3]     


    'Dbk'

"""
n = len(Gamma.vertices())
m = len(Gamma.edges())
ds = Gamma.degree_sequence()
Q = GraphQuery(display_cols=['graph6', 'aut_grp_size', 'degree_sequence'], num_edges=['=', m], num_vertices=["=", n])
for g in Q:
    if g.is_isomorphic(Gamma):
        if verbose:
            print("\n graphs with %s vertices"%n+" and %s edges:\n"%m)
            Q.show()
            print("\n")
        return g.graph6_string()

Let’s do the Landau shuffle

Posted on 2021/10/23 by wdjoyner

Here’s a shuffle I’ve not seen before:

Take an ordinary deck of 52 cards and place them, face up, in the following pattern:
Going from the top of the deck to the bottom, placing cards down left-to-right, put 13 cards in the top row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
11 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
then 9 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
then 7 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\$
then 5 cards in the next row:
$\Box\ \Box\ \Box\ \Box\ \Box\$
then 3 cards in the next row:
$\Box\ \Box\ \Box\$
and finally, the remaining 4 cards in the last row:
$\Box\ \Box\ \Box\ \Box\$
Now, take the left-most card in each row and move it to the right of the others (effectively, this is a cyclic shift of that row of cards to the left).
Finally, reassemble the deck by reversing the order of the placement.

In memory of the great German mathematician Edmund Landau (1877-1938, see also this bio), I call this the Landau shuffle. As with any card shuffle, this shuffle permutes the original ordering of the cards. To restore the deck to it’s original ordering you must perform this shuffle exactly 180180 times. (By the way, this is called the order of the shuffle.) Yes, one hundred eighty thousand, one hundred and eighty times. Moreover, no other shuffle than this Landau shuffle will require more repetitions to restore the deck. So, in some sense, the Landau shuffle is the shuffle that most effectively rearranges the cards.

Left to right: Oswald Veblen, Edmund Landau, Harald Bohr. Location, photographer, date unknown.

Now suppose we have a deck of $n$ (distictly labeled) cards, where $n>2$ is an integer. The collection of all possible shuffles, or permutations, of this deck is denoted $S_n$ and called the symmetric group. The above discussion leads naturally to the following question(s).

Question: What is the largest possible order of a shuffle of this deck (and how do you construct it)?

This requires a tiny bit of group theory. You only need to know that any permutation of $n$ symbols (such as the card deck above) can be decomposed into a composition or product) of disjoint cycles. To compute the order of an element $g \in S_n$ , write that element $g$ in disjoint cycle notation. Denote the lengths of the disjoint cycles occurring in $g$ as $k_1, k_2, \dots , k_m$ , where $k_i>0$ are integers forming a partition of $n$ : $n = k_1 + k_2 +\dots + k_m$ . Then the order of $g$ is known to be given by $order(g) = LCM(k_1, k_2, ...., k_m)$ , where LCM denotes the least common multiple.

The Landau function $g(n)$ is the function that returns the maximum possible order of an element $g \in S_n$ . Landau introduced this function in a 1903 paper where he also proved the asymptotic relation $\lim_{n\to \infty} \frac{\ln(g(n))}{\sqrt{n\ln(n)}}=1$ .

Example: If $n=52$ then note $52 = 13+11+9+7+5+3+4$ and that $LCM(13,11,9,77,5,3,4)=180180$ .

Oddly, my favorite mathematical software program SageMath does not have an implementation of the Landau function, so we end with some SageMath code.

def landau_function(n):
    L = Partitions(n).list()
    lcms = [lcm(P) for P in L]
    return max(lcms)

Here is an example (the time is included to show this took about 2 seconds on my rather old mac laptop):

sage: time landau_function(52) CPU times: user 1.91 s, sys: 56.1 ms, total: 1.97 s Wall time: 1.97 s 180180

The truncated tetrahedron covers the tetrahedron

Posted on 2021/04/29 by wdjoyner

At first, you might think this is obvious – just “clip” off each corner of the tetrahedron $\Gamma_1$ to create the truncated tetrahedron $\Gamma_2$ (by essentially creating a triangle from each of these clipped corners – see below for the associated graph). Then just map each such triangle to the corresponding vertex of the tetrahedron. No, it’s not obvious because the map just described is not a covering. This post describes one way to think about how to construct any covering.

First, color the vertices of the tetrahedron in some way.

The coloring below corresponds to a harmonic morphism $\phi : \Gamma_2\to \Gamma_1$ :

All others are obtained from this by permuting the colors. They are all covers of $\Gamma_1 = K_4$ – with no vertical multiplicities and all horizontal multiplicities equal to 1. These 24 harmonic morphisms of $\Gamma_2\to\Gamma_1$ are all coverings and there are no other harmonic morphisms.

Quartic graphs with 12 vertices

Posted on 2020/10/13 by wdjoyner

This is a continuation of the post A table of small quartic graphs. As with that post, it’s modeled on the handy wikipedia page Table of simple cubic graphs.

According to SageMath computations, there are 1544 connected, 4-regular graphs. Exactly 2 of these are symmetric (ie, arc transitive), also vertex-transitive and edge-transitive. Exactly 8 of these are vertex-transitive but not edge-transitive. None are distance regular.

Example 1: The first example of such a symmetric graph is the circulant graph with parameters (12, [1,5]), depicted below. It is bipartite, has girth 4, and its automorphism group has order 768, being generated by $(9,11), (5,6), (4,8), (2,10), (1,2)(5,9)(6,11)(7,10), (1,7), (0,1)(2,5)(3,7)(4,9)(6,10)(8,11)$ .

Example 2: The second example of such a symmetric graph is the cuboctahedral graph, depicted below. It has girth 3, chromatic number 3, and its automorphism group has order 48, being generated by $(1,10)(2,7)(3,6)(4,8)(9,11), (1,11)(3,4)(6,8)(9,10), (0,1,9)(2,8,10)(3,7,11)(4,5,6)$ .

A table of small quartic graphs

Posted on 2020/07/02 by wdjoyner

This page is modeled after the handy wikipedia page Table of simple cubic graphs of “small” connected 3-regular graphs, where by small I mean at most 11 vertices.

These graphs are obtained using the SageMath command graphs(n, [4]*n), where n = 5,6,7,… .

5 vertices: Let $V=\{0,1,2,3,4\}$ denote the vertex set. There is (up to isomorphism) exactly one 4-regular connected graphs on 5 vertices. By Ore’s Theorem, this graph is Hamiltonian. By Euler’s Theorem, it is Eulerian.
4reg5a: The only such 4-regular graph is the complete graph $\Gamma = K_5$ .
graph4reg5
We have

diameter = 1
girth = 3
If G denotes the automorphism group then G has cardinality 120 and is generated by (3,4), (2,3), (1,2), (0,1). (In this case, clearly, $G = S_5$ .)
edge set: $\{(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)\}$

6 vertices: Let $V=\{0,1,\dots, 5\}$ denote the vertex set. There is (up to isomorphism) exactly one 4-regular connected graphs on 6 vertices. By Ore’s Theorem, this graph is Hamiltonian. By Euler’s Theorem, it is Eulerian.
4reg6a: The first (and only) such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 2), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4), (2, 3), (2, 5), (3, 4), (3, 5), (4, 5)\}$ .
graph4reg6
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 48 and is generated by (2,4), (1,2)(4,5), (0,1)(3,5).

7 vertices: Let $V=\{0,1,\dots, 6\}$ denote the vertex set. There are (up to isomorphism) exactly 2 4-regular connected graphs on 7 vertices. By Ore’s Theorem, these graphs are Hamiltonian. By Euler’s Theorem, they are Eulerian.
4reg7a: The 1st such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 3), (0, 5), (0, 6), (1, 2), (1, 3), (1, 5), (2, 3), (2, 4), (2, 6), (3, 4), (4, 5), (4, 6), (5, 6)\}$ . This is an Eulerian, Hamiltonian (by Ore’s Theorem), vertex transitive (but not edge transitive) graph.
graph4reg7a
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 14 and is generated by (1,5)(2,4)(3,6), (0,1,3,2,4,6,5).

4reg7b: The 2nd such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 3), (0, 4), (0, 6), (1, 2), (1, 5), (1, 6), (2, 3), (2, 4), (2, 6), (3, 4), (3, 5), (4, 5), (5, 6)\}$ . This is an Eulerian, Hamiltonian graph (by Ore’s Theorem) which is neither vertex transitive nor edge transitive.
graph4reg7b
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 48 and is generated by (3,4), (2,5), (1,3)(4,6), (0,2)

8 vertices: Let $V=\{0,1,\dots, 7\}$ denote the vertex set. There are (up to isomorphism) exactly six 4-regular connected graphs on 8 vertices. By Ore’s Theorem, these graphs are Hamiltonian. By Euler’s Theorem, they are Eulerian.
4reg8a: The 1st such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 5), (0, 6), (0, 7), (1, 3), (1, 6), (1, 7), (2, 3), (2, 4), (2, 5), (2, 7), (3, 4), (3, 6), (4, 5), (4, 6), (5, 7)\}$ . This is vertex transitive but not edge transitive.
graph4reg8a
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 16 and is generated by $(1,7)(2,3)(5,6)$ and $(0,1)(2,4)(3,5)(6,7)$ .

4reg8b: The 2nd such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 5), (0, 6), (0, 7), (1, 3), (1, 6), (1, 7), (2, 3), (2, 4), (2, 5), (2, 7), (3, 4), (3, 6), (4, 5), (4, 6), (5, 7)\}$ . This is a vertex transitive (but not edge transitive) graph.
graph4reg8b
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 48 and is generated by $(2,3)(5,7)$ , $(1,3)(4,5)$ , $(0,1,3)(4,5,6)$ , $(0,4)(1,6)(2,5)(3,7)$ .

4reg8c: The 3rd such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 2), (0, 5), (0, 6), (1, 3), (1, 4), (1, 7), (2, 3), (2, 4), (2, 7), (3, 5), (3, 6), (4, 5), (4, 6), (5, 7), (6, 7)\}$ . This is a strongly regular (with “trivial” parameters (8, 4, 0, 4)), vertex transitive, edge transitive graph.
graph4reg8c
We have

diameter = 2
girth = 4
If G denotes the automorphism group then G has cardinality $1152=2^7\cdot 3^2$ and is generated by (5,6), (4,7), (3,4), (2,5), (1,2), (0,1)(2,3)(4,5)(6,7).

4reg8d: The 4th such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 2), (0, 4), (0, 6), (1, 3), (1, 5), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 6), (5, 7), (6, 7)\}$ . This graph is not vertex transitive, nor edge transitive.
graph4reg8d
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 16 and is generated by (3,5), (1,4), (0,2)(1,3)(4,5)(6,7), (0,6)(2,7).

4reg8e: The 5th such 4-regular graph is the graph $\Gamma$ having edge set: $\{(0, 1), (0, 2), (0, 6), (0, 7), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 7), (3, 5), (3, 7), (4, 5), (4, 6), (5, 6), (6, 7)\}$ . This graph is not vertex transitive, nor edge transitive.
graph4reg8e
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 4 and is generated by (0,1)(2,4)(3,6)(5,7), (0,2)(1,4)(3,6).

4reg8f: The 6th (and last) such 4-regular graph is the bipartite graph $\Gamma=K_{4,4}$ having edge set: $\{(0, 1), (0, 2), (0, 6), (0, 7), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 5), (3, 7), (4, 5), (4, 6), (5, 6), (5, 7), (6, 7)\}$ . This graph is not vertex transitive, nor edge transitive.
graph4reg8f
We have

diameter = 2
girth = 3
If G denotes the automorphism group then G has cardinality 12 and is generated by (3,4)(6,7), (1,2), (0,3)(5,6).

9 vertices: Let $V=\{0,1,\dots, 8\}$ denote the vertex set. There are (up to isomorphism) exactly 16 4-regular connected graphs on 9 vertices. Perhaps the most interesting of these is the strongly regular graph with parameters (9, 4, 1, 2) (also distance regular, as well as vertex- and edge-transitive). It has an automorphism group of cardinality 72, and is referred to as d4reg9-14 below.

Without going into details, it is possible to theoretically prove that there are no harmonic morphisms from any of these graphs to either the cycle graph $C_4$ or the complete graph $K_4$ . However, both d4reg9-3 and d4reg9-14 not only have harmonic morphisms to $C_3$ , they each may be regarded as a multicover of $C_3$ .

d4reg9-1
Gamma edges: E1 = [(0, 1), (0, 2), (0, 7), (0, 8), (1, 2), (1, 3), (1, 7), (2, 3), (2, 8), (3, 4), (3, 5), (4, 5), (4, 6), (4, 8), (5, 6), (5, 7), (6, 7), (6, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  12 
aut gp gens:  [(1,2)(4,5)(7,8), (0,1)(3,8)(5,6), (0,4)(1,5)(2,6)(3,7)]

d4reg9_1

d4reg9-2 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 3), (1, 7), (2, 3), (2, 5), (2, 8), (3, 4), (4, 5), (4, 6), (4, 8), (5, 6), (5, 7), (6, 7), (6, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  2 
aut gp gens:  [(0,5)(1,6)(2,8)(3,4)]

d4reg9_2

d4reg9-3 
Gamma edges: E1 = [(0, 1), (0, 2), (0, 7), (0, 8), (1, 2), (1, 3), (1, 4), (2, 3), (2, 8), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6), (5, 7), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  18 
aut gp gens:  [(1,7)(2,8)(3,6)(4,5), (0,1,4,6,8,2,3,5,7)]

d4reg9_3

d4reg9-4 
Gamma edges: E1 = [(0, 1), (0, 5), (0, 7), (0, 8), (1, 2), (1, 4), (1, 7), (2, 3), (2, 4), (2, 5), (3, 4), (3, 6), (3, 8), (4, 5), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  4 
aut gp gens:  [(2,4), (0,6)(1,3)(7,8)]

d4reg9_4

d4reg9-5 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 5), (0, 8), (1, 2), (1, 4), (1, 7), (2, 3), (2, 5), (2, 7), (3, 4), (3, 8), (4, 5), (4, 6), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  12 
aut gp gens:  [(1,5)(2,4)(6,7), (0,1)(2,3)(4,5)(7,8)]

d4reg9_5

d4reg9-6 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 5), (1, 6), (2, 3), (2, 5), (2, 6), (3, 4), (3, 8), (4, 5), (4, 7), (4, 8), (5, 6), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  8 
aut gp gens:  [(2,6)(3,7), (0,3)(1,2)(4,7)(5,6)]

d4reg9_6

d4reg9-7 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 4), (0, 8), (1, 2), (1, 3), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (4, 5), (4, 8), (5, 6), (5, 7), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  2 
aut gp gens:  [(0,3)(1,4)(2,8)(5,6)]

d4reg9_7

d4reg9-8 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 3), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (4, 5), (4, 6), (4, 8), (5, 6), (5, 8), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  2 
aut gp gens:  [(0,8)(1,5)(2,6)(3,4)]

d4reg9_8

d4reg9-9 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 6), (0, 8), (1, 2), (1, 3), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (4, 5), (4, 7), (4, 8), (5, 6), (5, 8), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  4 
aut gp gens:  [(5,7), (0,3)(2,6)(4,8)]

d4reg9_9

d4reg9-10 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 5), (0, 8), (1, 2), (1, 4), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 8), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  16 
aut gp gens:  [(2,6)(3,8), (1,5), (0,1)(2,3)(4,5)(6,8)]

d4reg9_10

d4reg9-11 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 4), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 5), (4, 5), (4, 8), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  8 
aut gp gens:  [(2,4)(7,8), (0,2)(3,7)(4,6)(5,8)]

d4reg9_11

d4reg9-12 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 6), (0, 8), (1, 2), (1, 4), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 8), (5, 6), (5, 8), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  18 
aut gp gens:  [(1,6)(2,5)(3,8)(4,7), (0,1,6)(2,7,3)(4,5,8), (0,2)(1,3)(5,8(6,7)]

d4reg9_12

d4reg9-13 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 4), (0, 8), (1, 2), (1, 5), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 8), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  8 
aut gp gens:  [(2,6)(3,8), (0,1)(2,3)(4,5)(6,8), (0,4)(1,5)]

d4reg9_13

d4reg9-14 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 4), (0, 8), (1, 2), (1, 5), (1, 8), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 6), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  72 
aut gp gens:  [(2,5)(3,4)(6,7), (1,3)(4,8)(5,7), (0,1)(2,3)(4,5)]

d4reg9_14

d4reg9-15 
Gamma edges: E1 = [(0, 1), (0, 4), (0, 6), (0, 8), (1, 2), (1, 3), (1, 5), (2, 3), (2, 4), (2, 7), (3, 4), (3, 7), (4, 5), (5, 6), (5, 8), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  32 
aut gp gens:  [(6,8), (2,3), (1,4), (0,1)(2,6)(3,8)(4,5)]

d4reg9_15

d4reg9-16 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 7), (3, 8), (4, 5), (4, 6), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  16 
aut gp gens:  [(7,8), (4,5), (0,1)(2,3)(4,7)(5,8), (0,2)(1,3)(4,7)(5,8)]

d4reg9_16

10 vertices: Let $V=\{0,1,\dots, 9\}$ denote the vertex set. There are (up to isomorphism) exactly 59 4-regular connected graphs on 10 vertices. One of these actually has an automorphism group of cardinality 1. According to SageMath: Only three of these are vertex transitive, two (of those 3) are symmetric (i.e., arc transitive), and only one (of those 2) is distance regular.

Example 1: The quartic, symmetric graph on 10 vertices that is not distance regular is depicted below. It has diameter 2, girth 4, chromatic number 3, and has an automorphism group of order 320 generated by $\{(7,8), (4,6), (1,2), (1,7)(2,8)(3,4)(5,6), (0,1,3,4,7)(2,5,6,8,9)\}$ .

d4reg10-46a

Example 2: The quartic, distance regular, symmetric graph on 10 vertices is depicted below. It has diameter 3, girth 4, chromatic number 2, and has an automorphism group of order 240 generated by $\{(2,5)(4,7), (2,8)(3,4), (1,5)(7,9), (0,1,3,2,7,6,9,8,4,5)\}$ .

d4reg10-51a

11 vertices: There are (up to isomorphism) exactly 265 4-regular connected graphs on 11 vertices. Only two of these are vertex transitive. None are distance regular or edge transitive.

Example 1: One of the vertex transitive graphs is depicted below. It has diameter 2, girth 4, chromatic number 3, and has an automorphism group of order 22 generated by $\{(1,10)(2,9)(3,4)(5,6)(7,8), (0,1,5,4,2,7,8,9,3,6,10)\}$ .

Example 2:The second vertex transitive graph is depicted below. It has diameter 3, girth 3, chromatic number 4, and has an automorphism group of order 22 generated by $\{(1,5)(2,7)(3,6)(4,8)(9,10), (0,1,3,2,4,10,9,8,7,6,5)\}$ .

Harmonic morphisms from cubic graphs of order 8 to a graph of order 4

Posted on 2020/06/08 by wdjoyner

There are five simple cubic graphs of order 8 (listed here) and there are 6 connected graphs of order 4 (listed here). But before we get started, I have a conjecture.

Let $\Gamma_1$ be a simple graph on n1 vertices, $\Gamma_2$ a simple graph on n2 vertices, and assume there is a harmonic morphism $\phi:\Gamma_1 \to \Gamma_2$ . Call an n1-tuple of “colors” $\{0,1,2,..., n2-1\}$ a harmonic color list (HCL) if it’s attached to a harmonic morphism in the usual way (the ith coordinate is j if $\phi$ sends vertex i of $\Gamma_1$ to vertex j of $\Gamma_2$ ). Let S be the set of all such HCLs. The automorphism group $G_1$ of $\Gamma_1$ acts on S (by permuting coordinates associated to the vertices of $\Gamma_1$ , as does the automorphism group $G_2$ of $\Gamma_2$ (by permuting the “colors” associated to the vertices of $\Gamma_2$ ). These actions commute. Clearly S decomposes as a disjoint union of distinct $G_1\times G_2$ orbits. The conjecture is that there is only one such orbit.

Note: Caroline Melles has disproven this conjecture. Still, the question of the number of orbits is an interesting one, IMHO.

Onto the topic of the post! The 6 connected graphs of order 4 are called P4 (the path graph), D3 (the star graph, also $K_{3,1}$ ), C4 (the cycle graph), K4 (the complete graph), Paw (C3 with a “tail”), and Diamond (K4 but missing an edge). All these terms are used on graphclasses.org. The results below were obtained using SageMath.

We start with the graph $\Gamma_1$ listed 1st on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [2, 2, -2, -2], 2). This graph $\Gamma_1$ has diameter 3, girth 3, and its automorphism group G is generated by (5,6), (1,2), (0,3)(4,7), (0,4)(1,5)(2,6)(3,7), $|G|=16$ . This graph is not vertex transitive. Its characteristic polynomial is $x^8 - 12x^6 - 8x^5 + 38x^4 + 48x^3 - 12x^2 - 40x - 15$ . Its edge connectivity and vertex connectivity are both 2. This graph has no non-trivial harmonic morphisms to D3 or P4 or C4 or Paw. However, there are 48 non-trivial harmonic morphisms to $\Gamma_2=K4$ . For example,
(the automorphism group of K4, ie the symmetric group of degree 4, acts on the colors {0,1,2,3} and produces 24 total plots), and (again, the automorphism group of K4, ie the symmetric group of degree 4, acts on the colors {0,1,2,3} and produces 24 total plots). There are 8 non-trivial harmonic morphisms to $\Gamma_2={\rm Diamond}$ . For example, and Here the automorphism group of K4, ie the symmetric group of degree 4, acts on the colors {0,1,2,3}, while the automorphism group of the graph $\Gamma_1$ acts by permuting some of the coordinates, for example, it can swap the 5th and 6th coordinates.Next, we take for $\Gamma_1$ the graph listed 2nd on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [4, -2, 4, 2], 2). This graph $\Gamma_1$ has diameter 3, girth 3, and its automorphism group G is generated by (1,7)(2,6)(3,5), (0,4)(1,3)(5,7), $|G|=4$ (obviously too small to act transitively on the vertices). Its characteristic polynomial is $x^8 - 12x^6 - 4x^5 + 38x^4 + 16x^3 - 36x^2 - 12x + 9$ , its edge connectivity and vertex connectivity are both 3. This graph has no non-trivial harmonic morphisms to D3 or P4 or C4 or Paw or K4. However, it has 4 non-trivial harmonic morphisms to Diamond. They are:
Let $\Gamma_1$ denote the graph listed 3rd on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [2, 4, -2, 3, 3, 4, -3, -3], 1). This graph $\Gamma_1$ has diameter 2, girth 3, and its automorphism group G is generated by (4,6), (1,2)(3,5), (0,1)(5,7), $|G|=12$ . It does not act transitively on the vertices. Its characteristic polynomial is $x^8 - 12x^6 - 2x^5 + 36x^4 - 31x^2 + 12x$ and its edge connectivity and vertex connectivity are both 3.
This graph has no non-trivial harmonic morphisms to P4 or C4 or Paw or K4 or Diamond. However, it has 6 non-trivial harmonic morphisms to D3, for example,

The automorphism group of D3 (the symmetric group of degree 3) acts by permuting the colors {0,1,2,3} and so yields a total of 6=3! such harmonic color plots.Let $\Gamma_1$ denote the graph listed 4th on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [4, -3, 3, 4], 2). This example is especially interesting. Otherwise known as the “cube graph” $Q_3$ , this graph $\Gamma_1$ has diameter 3, girth 4, and its automorphism group G is generated by ((2,4)(5,7), (1,7)(4,6), (0,1,4,5)(2,3,6,7), $|G|=48$ . It is vertex transitive. Its characteristic polynomial is $x^8 - 12x^6 + 30x^4 - 28x^2 + 9$ and its edge connectivity and vertex connectivity are both 3.
This graph has no non-trivial harmonic morphisms to D3 or P4 or Paw. However, it has 24 non-trivial harmonic morphisms to C4, 24 non-trivial harmonic morphisms to K4, and 24 non-trivial harmonic morphisms to Diamond. An example of a non-trivial harmonic morphism to K4:

A few examples of a non-trivial harmonic morphism to Diamond:
and
A few examples of a non-trivial harmonic morphism to C4:

The automorphism group of C4 acts by permuting the colors {0,1,2,3} cyclically, while the automorphism group G acts by permuting coordinates. These yield more harmonic color plots.

Harmonic morphisms to D_3 – examples

Posted on 2020/05/01 by wdjoyner

This post expands on a previous post and gives more examples of harmonic morphisms to the tree $\Gamma_2=D_3$ . This graph is also called a star graph $Star_3$ on 3+1=4 vertices, or the bipartite graph $K_{1,3}$ .
D3-0123

We indicate a harmonic morphism by a vertex coloring. An example of a harmonic morphism can be described in the plot below as follows: $\phi:\Gamma_1\to \Gamma_2=D_3$ sends the red vertices in $\Gamma_1$ to the red vertex of $\Gamma_2=D_3$ (we let 3 be the numerical notation for the color red), the blue vertices in $\Gamma_1$ to the blue vertex of $\Gamma_2=D_3$ (we let 2 be the numerical notation for the color blue), the green vertices in $\Gamma_1$ to the green vertex of $\Gamma_2=D_3$ (we let 1 be the numerical notation for the color green), and the white vertices in $\Gamma_1$ to the white vertex of $\Gamma_2=D_3$ (we let 0 be the numerical notation for the color white).

First, a simple remark about harmonic morphisms in general: roughly speaking, they preserve adjacency. Suppose $\phi:\Gamma_1\to \Gamma_2$ is a harmonic morphism. Let $v,w\in V_1$ be adjacent vertices of $\Gamma_1$ . Then either (a) $\phi(v)=\phi(w)$ and $\phi$ “collapses” the edge (vertical) $(v,w)$ or (b) $\phi(v)\not= \phi(w)$ and the vertices $\phi(v)$ and $\phi(w)$ are adjacent in $\Gamma_2$ . In the particular case of this post (ie, the case of $\Gamma_2=D_3$ ), this remark has the following consequence: since in $D_3$ the green vertex is not adjacent to the blue or red vertex, none of the harmonic colored graphs below can have a green vertex adjacent to a blue or red vertex. In fact, any colored vertex can only be connected to a white vertex or a vertex of like color.

To get the following data, I wrote programs in Python using SageMath.

Example 1: There are only the 4 trivial harmonic morphisms $Star_4 \to D_3$ , plus the “obvious” ones obtained from that below and those induced by permutations of the vertices:
Star4-D3-00321 .

My guess is that the harmonic morphisms $Star_5\to D_3$ can be described in a similar manner. Likewise for the higher $Star_n$ graphs. Given a star graph $\Gamma$ with a harmonic morphism to $D_3$ , a leaf (connected to the center vertex 0) can be added to $\Gamma$ and preserve “harmonicity” if its degree 1 vertex is colored 0. You can try to “collapse” such leafs, without ruining the harmonicity property.

Example 2: For graphs like $\Gamma_1=$
C3LeafLeafLeaf-D3-000321
there are only the 4 trivial harmonic morphisms $\Gamma_1 \to D_3$ , plus the “obvious” ones obtained from that above and those induced by permutations of the vertices with a non-zero color.

Example 2.5: Likewise, for graphs like $\Gamma_1=$
3C3-D3-0332211
there are only the 4 trivial harmonic morphisms $\Gamma_1 \to D_3$ , plus the “obvious” ones obtained from that above and those induced by permutations of the vertices with a non-zero color.

Example 3: This is really a non-example. There are no harmonic morphisms from the (3-dimensional) cube graph (whose vertices are those of the unit cube) to $D_3$ .
More generally, take two copies of a cyclic graph on n vertices, $C_n$ , one hovering over the other. Now, connect each vertex of the top copy to the corresponding vertex of the bottom copy. This is a cubic graph that can be visualized as a “thick” regular polygon. (The cube graph is the case $n=4$ .) I conjecture that there is no harmonic morphism from such a graph to $D_3$ .

Example 4: There are 30 non-trivial harmonic morphisms $\Gamma_1 \to D_3$ for the Peterson graph (the last of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page). Here is an example:
petersen-D3-0330120021
Another interesting fact is that this graph has an automorphism group (isomorphic to the symmetric group on 5 letters) which acts transitively on the vertices.

Example 5: There are 12 non-trivial harmonic morphisms $\Gamma_1=K_{3,3} \to D_3$ for the complete bipartite (“utility”) graph $K_{3,3}$ . They are all obtained from either
K_3_3-D3-321000
or
K_3_3-D3-000231
by permutations of the vertices with a non-zero color (3!+3!=12).

Example 6: There are 6 non-trivial harmonic morphisms $\Gamma_1 \to D_3$ for the cubic graph $\Gamma_1=(V,E)$ , where $V=\{0,1,\dots, 9\}$ and $E = \{(0, 3), (0, 4), (0, 6), (1, 2), (1, 5), (1, 9), (2, 3), (2, 7), (3, 6), (4, 5), (4, 9), (5, 8), (6, 7), (7, 8), (8, 9)\}$ . This graph has diameter 3, girth 3, and edge-connectivity 3. It’s automorphism group is size 4, generated by (5,9) and (1,8)(2,7)(3,6). The harmonic morphisms are all obtained from
random3regular10e-D3-1011031102
by permutations of the vertices with a non-zero color (3!=6). This graph might be hard to visualize but it is isomorphic to the simple cubic graph having LCF notation [−4, 3, 3, 5, −3, −3, 4, 2, 5, −2]:
random3regular10e2
which has a nice picture. This is the ninth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page.

Example 7: (a) The first of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10f
This graph has diameter 5, automorphism group generated by (7,8), (6,9), (3,4), (2,5), (0,1)(2,6)(3,7)(4,8)(5,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(b) The second of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10g
This graph has diameter 4, girth 3, automorphism group generated by (7,8), (0,5)(1,2)(6,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(c) The third of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10h
This graph has diameter 3, girth 3, automorphism group generated by (4,5), (0,1)(8,9), (0,8)(1,9)(2,7)(3,6). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 8: The fourth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10i
This graph has diameter 3, girth 3, automorphism group generated by (4,6), (3,5), (1,8)(2,7)(3,4)(5,6), (0,9). There are 12 non-trivial harmonic morphisms $\Gamma_1\to D_3$ . For example,
3regular10i-D3-2220301022
and the remaining (3!=6 total) colorings obtained by permutating the non-zero colors. Another example is
3regular10i-D3-1103020111
and the remaining (3!=6 total) colorings obtained by permutating the non-zero colors.

Example 9: (a) The fifth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10j
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2,2,-2,-2,5],2) There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(b) The sixth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10k
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2,3,-2,5,-3],2) There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 10: The seventh of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10l-D3-3330222010
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2,3,-2,5,-3],2). Its automorphism group is order 12, generated by (1,2)(3,7)(4,6), (0,1)(5,6)(7,9), (0,4)(1,6)(2,5)(3,9). There are 6 non-trivial harmonic morphisms $\Gamma_1\to D_3$ , each obtained from the one above by permuting the non-zero colors.

Example 11: The eighth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10m
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, 3, 5, -4, -3, 5, 2, 5, -2, 4],1). Its automorphism group is order 2, generated by (0,3)(1,4)(2,5)(6,7). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 12: (a) The tenth (recall the 9th was mentioned above) of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10o
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[3, -3, 5, -3, 2, 4, -2, 5, 3, -4],1). Its automorphism group is order 6, generated by (2,8)(3,9)(4,5), (0,2)(5,6)(7,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(b) The 11th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10p
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[-4, 4, 2, 5, -2],2). Its automorphism group is order 4, generated by (0,1)(2,9)(3,8)(4,7)(5,6), (0,5)(1,6)(2,7)(3,8)(4,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(c) The 12th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10q
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -2, 2, 4, -2, 5, 2, -4, -2, 2],1). Its automorphism group is order 6, generated by (1,9)(2,8)(3,7)(4,6), (0,4,6)(1,3,8)(2,7,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(d) The 13th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10r
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2, 5, -2, 5, 5],2). Its automorphism group is order 8, generated by (4,8)(5,7), (0,2)(3,9), (0,5)(1,6)(2,7)(3,8)(4,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 13: The 14th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10s-D3-2033020110
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. Another harmonic morphism $\Gamma_1\to D_3$ is depicted as:
3regular10s-D3-0302222201
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. And another harmonic morphism $\Gamma_1\to D_3$ is depicted as:
3regular10s-D3-1110302011
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -3, -3, 3, 3],2). Its automorphism group is order 48, generated by (4,6), (2,8)(3,7), (1,9), (0,2)(3,5), (0,3)(1,4)(2,5)(6,9)(7,8). There are a total of 18=3!+3!+3! non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 14: The 15th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10t-D3-2033020110
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -4, 4, -4, 4],2). Its automorphism group is order 8, generated by (2,7)(3,8), (1,9)(2,3)(4,6)(7,8), (0,5)(1,4)(2,3)(6,9)(7,8). There are a total of 6=3! non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 15: (a) The 16th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10u
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -4, 4, 5, 5],2). Its automorphism group is order 4, generated by (0,3)(1,2)(4,9)(5,8)(6,7), (0,5)(1,6)(2,7)(3,8)(4,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(b) The 17th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10v
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, 5, -3, 5, 3],2). Its automorphism group is order 20, generated by (2,6)(3,7)(4,8)(5,9), (0,1)(2,5)(3,4)(6,9)(7,8), (0,2)(1,9)(3,5)(6,8). This group acts transitively on the vertices. There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(c) The 18th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10w
This is an example of a “thick polygon” graph, already mentioned in Example 3 above. Its SageMath command is Gamma1 = graphs.LCFGraph(10,[-4, 4, -3, 5, 3],2). Its automorphism group is order 20, generated by (2,5)(3,4)(6,9)(7,8), (0,1)(2,6)(3,7)(4,8)(5,9), (0,2)(1,9)(3,6)(4,7)(5,8). This group acts transitively on the vertices. There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(d) The 19th in the list of 19 is the Petersen graph, already in Example 4 above.

We now consider some examples of the cubic graphs having 12 vertices. According to the House of Graphs there are 109 of these, but we use the list on this wikipedia page.

Example 16: I wrote a SageMath program that looked for harmonic morphisms on a case-by-case basis. If there is no harmonic morphism $\Gamma_1\to D_3$ then, instead of showing a graph, I’ll list the edges (of course, the vertices are 0,1,…,11) and the SageMath command for it.

$\Gamma_1=(V_1,E_1)$ , where $E_1=\{ (0, 1), (0, 2), (0, 11), (1, 2), (1, 6), (2, 3), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)\}$ .
SageMath command:
V1 = [0,1,2,3,4,5,6,7,8,9,10,11] E1 = [(0, 1), (0, 2), (0, 11), (1, 2), (1, 6), (2, 3), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)] Gamma1 = Graph([V1,E1])
(Not in LCF notation since it doesn’t have a Hamiltonian cycle.)
$\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0, 1), (0, 6), (0, 11), (1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)\}$ .
SageMath command:
V1 = [0,1,2,3,4,5,6,7,8,9,10,11] E1 = [(0, 1), (0, 6), (0, 11), (1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)] Gamma1 = Graph([V1,E1])
(Not in LCF notation since it doesn’t have a Hamiltonian cycle.)
$\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0,1),(0,3),(0,11),(1,2),(1,6),(2,3),(2,5),(3,4),(4,5),(4,6),(5,6),(7,8),(7,9),(7,11),(8,9),(8,10),(9,10),(10,11)\}$ .
SageMath command:
V1 = [0,1,2,3,4,5,6,7,8,9,10,11] E1 = [(0,1),(0,3),(0,11),(1,2),(1,6),(2,3),(2,5),(3,4),(4,5),(4,6),(5,6),(7,8),(7,9),(7,11),(8,9),(8,10),(9,10),(10,11)] Gamma1 = Graph([V1,E1])
(Not in LCF notation since it doesn’t have a Hamiltonian cycle.)
This example has 12 non-trivial harmonic morphisms.
SageMath command:
V1 = [0,1,2,3,4,5,6,7,8,9,10,11] E1 = [(0,1),(0,3),(0,11),(1,2),(1,6),(2,3),(2,5),(3,4),(4,5),(4,6),(5,6),(7,8),(7,9),(7,11),(8,9),(8,10),(9,10),(10,11)] Gamma1 = Graph([V1,E1])
(Not in LCF notation since it doesn’t have a Hamiltonian cycle.) We show two such morphisms:

The other non-trivial harmonic morphisms are obtained by permuting the non-zero colors. There are 3!=6 for each graph above, so the total number of harmonic morphisms (including the trivial ones) is 6+6+4=16.
$\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0, 1), (0, 3), (0, 11), (1, 2), (1, 11), (2, 3), (2, 10), (3, 4), (4, 5), (4, 8), (5, 6), (5, 7), (6, 7), (6, 9), (7, 8), (8, 9), (9, 10), (10, 11)\}$ .
SageMath command:
Gamma1 = graphs.LCFGraph(12, [3, -2, -4, -3, 4, 2], 2)
This example has 12 non-trivial harmonic morphisms. $\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0, 1), (0, 3), (0, 11), (1, 2), (1, 11), (2, 3), (2, 10), (3, 4), (4, 5), (4, 7), (5, 6), (5, 8), (6, 7), (6, 9), (7, 8), (8, 9), (9, 10), (10, 11)\}$ . (This only differs by one edge from the one above.)
SageMath command:
Gamma1 = graphs.LCFGraph(12, [3, -2, -4, -3, 3, 3, 3, -3, -3, -3, 4, 2], 1)
We show two such morphisms:

And here is another plot of the last colored graph:

The other non-trivial harmonic morphisms are obtained by permuting the non-zero colors. There are 3!=6 for each graph above, so the total number of harmonic morphisms (including the trivial ones) is 6+6+4=16.
$\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0, 1), (0, 4), (0, 11), (1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7), (6, 8), (7, 8), (7, 10), (8, 9), (9, 10), (9, 11), (10, 11)\}$ .
SageMath command:
Gamma1 = graphs.LCFGraph(12, [4, 2, 3, -2, -4, -3, 2, 3, -2, 2, -3, -2], 1)
This example has 48 non-trivial harmonic morphisms. $\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0, 1), (0, 3), (0, 11), (1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7), (6, 9), (7, 8), (7, 10), (8, 9), (8, 11), (9, 10), (10, 11)\}$ .
SageMath command:
Gamma1 = graphs.LCFGraph(12, [3, 3, 3, -3, -3, -3], 2)
This example is also interesting as it has a large number of automorphisms – its automorphism group is size 64, generated by (8,10), (7,9), (2,4), (1,3), (0,5)(1,2)(3,4)(6,11)(7,8)(9,10), (0,6)(1,7)(2,8)(3,9)(4,10)(5,11). Here are examples of some of the harmonic morphisms using vertex-colored graphs:

I think all the other non-trivial harmonic morphisms are obtained by (a) permuting the non-zero colors, or (b) applying a element of the automorphism group of the graph.
(list under construction)