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.

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.

The Riemann-Hurwitz formula for regular graphs

Posted on 2020/08/21 by wdjoyner

A little over 10 years ago, M. Baker and S. Norine (I’ve also seen this name spelled Norin) wrote a terrific paper on harmonic morphisms between simple, connected graphs (see “Harmonic morphisms and hyperelliptic graphs” – you can find a downloadable pdf on the internet of you google for it). Roughly speaking, a harmonic function on a graph is a function in the kernel of the graph Laplacian. A harmonic morphism between graphs is, roughly speaking, a map from one graph to another that preserves harmonic functions.

They proved quite a few interesting results but one of the most interesting, I think, is their graph-theoretic analog of the Riemann-Hurwitz formula. We define the genus of a simple connected graph $\Gamma = (V,E)$ to be

${\rm genus}(\Gamma) = |E| - |V | + 1.$

It represents the minimum number of edges that must be removed from the graph to make it into a tree (so, a tree has genus 0).

Riemann-Hurwitz formula (Baker and Norine): Let $\phi:\Gamma_2\to \Gamma_1$ be a harmonic morphism from a graph $\Gamma_2 = (V_2,E_2)$ to a graph $\Gamma_1 = (V_1, E_1)$ . Then

${\rm genus}(\Gamma_2)-1 = {\rm deg}(\phi)({\rm genus}(\Gamma_1)-1)+\sum_{x\in V_2} [m_\phi(x)+\frac{1}{2}\nu_\phi(x)-1].$

I’m not going to define them here but $m_\phi(x)$ denotes the horizontal multiplicity and $\nu_\phi(x)$ denotes the vertical multiplicity.

I simply want to record a very easy corollary to this, assuming $\Gamma_2 = (V_2,E_2)$ is $k_2$ -regular and $\Gamma_1 = (V_1, E_1)$ is $k_1$ -regular.

Corollary: Let $\Gamma_2 \rightarrow \Gamma_1$ be a non-trivial harmonic morphism from a connected $k_2$ -regular graph
to a connected $k_1$ -regular graph.
Then

$\sum_{x\in V_2}\nu_\phi(x) = k_2|V_2| - k_1|V_1|\deg (\phi).$

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)

Harmonic morphisms to P_4 – examples

Posted on 2020/03/17 by wdjoyner

This post expands on a previous post and gives more examples of harmonic morphisms to the path graph $\Gamma_2=P_4$ .
path4-0123

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=P_4$ ), this remark has the following consequence: since in $P_4$ 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, $C_k$ 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 $\phi:\Gamma_1 \to \Gamma_2=P_k$ be a harmonic morphism from a graph $\Gamma_1$ with $n=|V_1|$ vertices to the path graph having $k>2$ vertices. Let $f:V_2 \to V_1$ be the coloring map (identified with an n-tuple whose coordinates are in $\{0,1,\dots ,k-1\}$ ). Associated to f is a partition $\Pi_f=[n_0,\dots,n_{k-1}]$ of n (here $[...]$ is a multi-set, so repetition is allowed but the ordering is unimportant): $n=n_0+n_1+...+n_{k-1}$ , where $n_j$ 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 $\phi:\Gamma_1 \to P_k$ , $\phi:\Gamma'_1 \to P_k$ , with associated
colorings $f, f'$ whose corresponding partitions agree, $\Pi_f=\Pi_{f'}$ then we say $f'$ and $f$ 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 $\Gamma_1 \to P_4$ examples!

There are no non-trivial harmonic morphisms $C_5 \to P_4$ , so we start with $C_6$ . 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=P_4$ sends the red vertices in $\Gamma_1$ to the red vertex of $\Gamma_2=P_4$ (we let 3 be the numerical notation for the color red), the blue vertices in $\Gamma_1$ to the blue vertex of $\Gamma_2=P_4$ (we let 2 be the numerical notation for the color blue), the green vertices in $\Gamma_1$ to the green vertex of $\Gamma_2=P_4$ (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=P_4$ (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 $C_6 \to P_4$ , plus that induced by $f = (1, 2, 3, 2, 1, 0)$ and all of its cyclic permutations (4+6=10). This set of 6 permutations is closed under the automorphism of $P_4$ induced by the transposition (0,3)(1,2) (so total = 10). cyclic6-123210

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

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

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

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 $P_4$ .

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 $\Gamma_1$ having a harmonic morphism $\phi:\Gamma_1\to P_4$ 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 $\phi:\Gamma_1\to P_4$ . They are depicted as follows:
3regular10nn-P4-1112322210
3regular10nn-P4-1112223210
3regular10nn-P4-1012322211
3regular10nn-P4-1012223211
3regular10nn-P4-2321110122
3regular10nn-P4-2321011122
3regular10nn-P4-2221110123
3regular10nn-P4-2221011123
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 $\Gamma_1\to P_4$ 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.)
$\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)
$\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)\}$ .
SageMath command:
Gamma1 = graphs.LCFGraph(12, [3, -2, -4, -3, 3, 3, 3, -3, -3, -3, 4, 2], 1)
$\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)
$\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)
(list under construction)

Harmonic morphisms to P_3 – examples

Posted on 2020/02/06 by wdjoyner

This post expands on a previous post and gives more examples of harmonic morphisms to the path graph $\Gamma_2=P_3$ .

The path graph P_3

If $\Gamma_1 = (V_1, E_1)$ and $\Gamma_2 = (V_2, E_2)$ are graphs then a map $\phi:\Gamma_1\to \Gamma_2$ (that is, $\phi: V_1\cup E_1\to V_2\cup E_2$ ) is a morphism provided

if $\phi$ sends an edge to an edge then the edges vertices must also map to each other: $e=(v,w)\in E_1$ and $\phi(e)\in E_2$ then $\phi(e)$ is an edge in $\Gamma_2$ having vertices $\phi(v)\in V_2$ and $\phi(w)\in V_2$ , where $\phi(v)\not= \phi(w)$ , and
if $\phi$ sends an edge to a vertex then the edges vertices must also map to that vertex: if $e=(v,w)\in E_1$ and $\phi(e)\in V_2$ then $\phi(e) = \phi(v) = \phi(w)$ .

As a non-example, if $\Gamma_1$ is a planar graph, if $\Gamma_2$ is its dual graph, and if $\phi:\Gamma_1\to\Gamma_2$ is the dual map $V_1\to E_2$ and $E_1\to V_2$ , then $\phi$ is not a morphism.

Given a map $\phi_E : E_1 \rightarrow E_2 \cup V_2$ , an edge $e_1$ is called horizontal if $\phi_E(e_1) \in E_2$ and is called vertical if $\phi_E(e_1) \in V_2$ . We say that a graph morphism $\phi: \Gamma_1 \rightarrow \Gamma_2$ is a graph homomorphism if $\phi_E (E_1) \subset E_2$ . Thus, a graph morphism is a homomorphism if it has no vertical edges.

Suppose that $\Gamma_2$ has at least one edge. Let $Star_{\Gamma_1}(v)$ denote the star subgraph centered at the vertex v. A graph morphism $\phi : \Gamma_1 \to \Gamma_2$ is called harmonic if for all vertices $v \in V(\Gamma_1)$ , the quantity
$\mu_\phi(v,f)= |\phi^{-1}(f) \cap Star_{\Gamma_1}(v)|$
(the number of edges in $\Gamma_1$ adjacent to $v$ and mapping to the edge $f$ in $\Gamma_2$ ) is independent of the choice of edge $f$ in $Star_{\Gamma_2}(\phi(v))$ .

An example of a harmonic morphism can be described in the plot below as follows: $\phi:\Gamma_1\to \Gamma_2=P_3$ sends the red vertices in $\Gamma_1$ to the red vertex of $\Gamma_2=P_3$ , the green vertices in $\Gamma_1$ to the green vertex of $\Gamma_2=P_3$ , and the white vertices in $\Gamma_1$ to the white vertex of $\Gamma_2=P_3$ .

Example 1:

P3-C3-V

Example 2:
D3-2110

Example 3:
cyclic4-2101

Examples of graph-theoretic harmonic morphisms using Sage

Posted on 2015/04/09 by wdjoyner

In the case of simple graphs (without multiple edges or loops), a map $f$ between graphs $\Gamma_2 = (V_2,E_2)$ and $\Gamma_1 = (V_1, E_1)$ can be uniquely defined by specifying where the vertices of $\Gamma_2$ go. If $n_2 = |V_2|$ and $n_1 = |V_1|$ then this is a list of length $n_2$ consisting of elements taken from the $n_1$ vertices in $V_1$ .

Let’s look at an example.

Example: Let $\Gamma_2$ denote the cube graph in ${\mathbb{R}}^3$ and let $\Gamma_1$ denote the “cube graph” (actually the unit square) in ${\mathbb{R}}^2$ .

This is the 3-diml cube graph $\Gamma_2$ in Sagemath

The cycle graph $\Gamma_1$ on 4 vertices (also called the cube graph in 2-dims, created using Sagemath.

We define a map $f:\Gamma_2\to \Gamma_1$ by

f = [[‘000’, ‘001’, ‘010’, ‘011’, ‘100’, ‘101’, ‘110’, ‘111’], [“00”, “00”, “01”, “01”, “10”, “10”, “11”, “11”]].

Definition: For any vertex $v$ of a graph $\Gamma$ , we define the star $St_\Gamma(v)$ to be a subgraph of $\Gamma$ induced by the edges incident to $v$ . A map $f : \Gamma_2 \to \Gamma_1$ is called harmonic if for all vertices $v' \in V(\Gamma_2)$ , the quantity

$|\phi^{-1}(e) \cap St_{\Gamma_2}(v')|$

is independent of the choice of edge $e$ in $St_{\Gamma_1}(\phi(v'))$ .

Here is Python code in Sagemath which tests if a function is harmonic:

def is_harmonic_graph_morphism(Gamma1, Gamma2, f, verbose = False):
    """
    Returns True if f defines a graph-theoretic mapping
    from Gamma2 to Gamma1 that is harmonic, and False otherwise. 

    Suppose Gamma2 has n vertices. A morphism 
              f: Gamma2 -> Gamma1
    is represented by a pair of lists [L2, L1],
    where L2 is the list of all n vertices of Gamma2,
    and L1 is the list of length n of the vertices
    in Gamma1 that form the corresponding image under
    the map f.

    EXAMPLES:
        sage: Gamma2 = graphs.CubeGraph(2)
        sage: Gamma1 = Gamma2.subgraph(vertices = ['00', '01'], edges = [('00', '01')])
        sage: f = [['00', '01', '10', '11'], ['00', '01', '00', '01']]
        sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f)
        True
        sage: Gamma2 = graphs.CubeGraph(3)
        sage: Gamma1 = graphs.TetrahedralGraph()
        sage: f = [['000', '001', '010', '011', '100', '101', '110', '111'], [0, 1, 2, 3, 3, 2, 1, 0]]
        sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f)
        True
        sage: Gamma2 = graphs.CubeGraph(3)
        sage: Gamma1 = graphs.CubeGraph(2)
        sage: f = [['000', '001', '010', '011', '100', '101', '110', '111'], ["00", "00", "01", "01", "10", "10", "11", "11"]]
        sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f)
        True
        sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f, verbose=True)
        This [, ]] passes the check: ['000', [1, 1]]
        This [, ]] passes the check: ['001', [1, 1]]
        This [, ]] passes the check: ['010', [1, 1]]
        This [, ]] passes the check: ['011', [1, 1]]
        This [, ]] passes the check: ['100', [1, 1]]
        This [, ]] passes the check: ['101', [1, 1]]
        This [, ]] passes the check: ['110', [1, 1]]
        This [, ]] passes the check: ['111', [1, 1]]
        True
        sage: Gamma2 = graphs.TetrahedralGraph()
        sage: Gamma1 = graphs.CycleGraph(3)
        sage: f = [[0,1,2,3],[0,1,2,0]]
        sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f)
        False
        sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f, verbose=True)
        This [, ]] passes the check: [0, [1, 1]]
        This [, ]] fails the check: [1, [2, 1]]
        This [, ]] fails the check: [2, [2, 1]]
        False

    """
    V1 = Gamma1.vertices()
    n1 = len(V1)
    V2 = Gamma2.vertices()
    n2 = len(V2)
    E1 = Gamma1.edges()
    m1 = len(E1)
    E2 = Gamma2.edges()
    m2 = len(E2)
    edges_in_common = []
    for v2 in V2:
        w = image_of_vertex_under_graph_morphism(Gamma1, Gamma2, f, v2)
        str1 = star_subgraph(Gamma1, w)
        Ew = str1.edges()
        str2 = star_subgraph(Gamma2, v2)
        Ev2 = str2.edges()
        sizes = []
        for e in Ew:
            finv_e = preimage_of_edge_under_graph_morphism(Gamma1, Gamma2, f, e)
            L = [x for x in finv_e if x in Ev2]
            sizes.append(len(L))
            #print v2,e,L
        edges_in_common.append([v2, sizes])
    ans = True
    for x in edges_in_common:
        sizes = x[1]
        S = Set(sizes)
        if S.cardinality()>1:
            ans = False
            if verbose and ans==False:
                print "This [, ]] fails the check:", x
        if verbose and ans==True:
            print "This [, ]] passes the check:", x
    return ans

For further details (e.g., code to

star_subgraph

, etc), just ask in the comments.

Yet Another Mathblog

Category Archives: harmonic morphisms