This post expands on a previous post and gives more examples of harmonic morphisms to the path graph .

First, a simple remark about harmonic morphisms in general: *roughly speaking, they preserve adjacency*. Suppose is a harmonic morphism. Let be adjacent vertices of . Then either (a) and “collapses” the edge (vertical) or (b) and the vertices and are adjacent in . In the particular case of this post (ie, the case of ), this remark has the following *consequence*: since in the white vertex is not adjacent to the blue or red vertex, none of the harmonic colored graphs below can have a white vertex adjacent to a blue or red vertex.

We first consider the *cyclic graph* on k vertices, as the domain in this post. However, before we get to examples (obtained by using SageMath), I’d like to state a (probably naive) conjecture.

Let be a harmonic morphism from a graph with vertices to the path graph having vertices. Let be the coloring map (identified with an n-tuple whose coordinates are in ). Associated to f is a partition of n (here is a multi-set, so repetition is allowed but the ordering is unimportant): , where is the number of times j occurs in f. We call this the *partition invariant* of the harmonic morphism.

**Definition**: For any two harmonic morphisms , , with associated

colorings whose corresponding partitions agree, then we say and are *partition equivalent*.

What can be said about partition equivalent harmonic morphisms? Caroline Melles has given examples where partition equivalent harmonic morphisms are not induced from an automorphism.

Now onto the examples!

There are no non-trivial harmonic morphisms , so we start with . We indicate a harmonic morphism by a vertex coloring. An example of a harmonic morphism can be described in the plot below as follows: sends the red vertices in to the red vertex of (we let 3 be the numerical notation for the color red), the blue vertices in to the blue vertex of (we let 2 be the numerical notation for the color blue), the green vertices in to the green vertex of (we let 1 be the numerical notation for the color green), and the white vertices in to the white vertex of (we let 0 be the numerical notation for the color white).

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

**Example 1**: There are only the 4 trivial harmonic morphisms , plus that induced by and all of its cyclic permutations (4+6=10). This set of 6 permutations is closed under the automorphism of induced by the transposition (0,3)(1,2) (so total = 10).

**Example 2**: There are only the 4 trivial harmonic morphisms, plus and all of its cyclic permutations (4+7=11). This set of 7 permutations is not closed under the automorphism of induced by the transposition (0,3)(1,2), so one also has and all 7 of its cyclic permutations (total = 7+11 = 18).

**Example 3**: There are only the 4 trivial harmonic morphisms, plus and all of its cyclic permutations (4+8=12). This set of 8 permutations is not closed under the automorphism of induced by the transposition (0,3)(1,2), so one also has and all of its cyclic permutations (12+8=20). In addition, there is and all of its cyclic permutations (20+8 = 28). The latter set of 8 cyclic permutations of is closed under the transposition (0,3)(1,2) (total = 28).

**Example 4**: There are only the 4 trivial harmonic morphisms, plus and all of its cyclic permutations (4+9=13). This set of 9 permutations is not closed under the automorphism of induced by the transposition (0,3)(1,2), so one also has and all 9 of its cyclic permutations (9+13 = 22). This set of 9 permutations is not closed under the automorphism of induced by the transposition (0,3)(1,2), so one also has and all 9 of its cyclic permutations (9+22 = 31). This set of 9 permutations is not closed under the automorphism of induced by the transposition (0,3)(1,2), so one also has and all 9 of its cyclic permutations (total = 9+31 = 40).

Next we consider some cubic graphs.

**Example 5**: There are 5 cubic graphs on 8 vertices, as listed on this wikipedia page. I wrote a SageMath program that looked for harmonic morphisms on a case-by-case basis. There are no non-trivial harmonic morphisms from any one of these 5 graphs to .

**Example 6**: There are 19 cubic graphs on 10 vertices, as listed on this wikipedia page. I wrote a SageMath program that looked for harmonic morphisms on a case-by-case basis. The *only one* of these 19 cubic graphs having a harmonic morphism is the graph whose SageMath command is `graphs.LCFGraph(10,[5, -3, -3, 3, 3],2)`

. It has diameter 3, girth 4, and automorphism group of 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 eight non-trivial harmonic morphisms . They are depicted as follows:

Note that the last four are obtained from the first 4 by applying the permutation (0,3)(1,2) to the colors (where 0 is white, etc, as above).

We move to cubic graphs on 12 vertices. There are quite a few of them – according to the House of Graphs page on connected cubic graphs, there are 109 of them (if I counted correctly).

**Example 7**: The cubic graphs on 12 vertices are listed on this wikipedia page. I wrote a SageMath program that looked for harmonic morphisms on a case-by-case basis. If there is *no harmonic morphism* 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.

- , where .

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.) - , where .

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.) - , where .

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.) - , where .

SageMath command:

`Gamma1 = graphs.LCFGraph(12, [3, -2, -4, -3, 4, 2], 2)`

- , where .

SageMath command:

`Gamma1 = graphs.LCFGraph(12, [3, -2, -4, -3, 3, 3, 3, -3, -3, -3, 4, 2], 1)`

- , where .

SageMath command:

`Gamma1 = graphs.LCFGraph(12, [4, 2, 3, -2, -4, -3, 2, 3, -2, 2, -3, -2], 1)`

- , where .

SageMath command:

`Gamma1 = graphs.LCFGraph(12, [3, 3, 3, -3, -3, -3], 2)`

- (list under construction)

You must be logged in to post a comment.