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

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.

  1. 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,
    3regular8a-K4-32103210 (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 3regular8a-K4-01230213 (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, 3regular8a-Diamond-12033201 and 3regular8a-Diamond-10233201Here 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:
    3regular8b-Diamond-32103210 3regular8b-Diamond-301230123regular8b-Diamond-123012303regular8b-Diamond-10321032Let \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,
    3regular8c-D3-33302010
    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:


    3regular8d-K4-31230210 A few examples of a non-trivial harmonic morphism to Diamond:
    3regular8d-Diamond-23320110 and
    3regular8d-Diamond-33210210 A few examples of a non-trivial harmonic morphism to C4:
    3regular8d-C4-12332100 3regular8d-C4-03322110 3regular8d-C4-33012210

    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.