In the case of simple graphs (without multiple edges or loops), a map between graphs and can be uniquely defined by specifying where the vertices of go. If and then this is a list of length consisting of elements taken from the vertices in .

Let’s look at an example.

**Example**: Let denote the cube graph in and let denote the “cube graph” (actually the unit square) in .

We define a map by

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

**Definition**: For any vertex of a graph , we define the *star* to be a subgraph of induced by the edges incident to . A map is called *harmonic* if for all vertices , the quantity

is independent of the choice of edge in .

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.

You must be logged in to post a comment.