String representation of trivalent 2-stratifolds with trivial fundamental group

Myriam Hernández-Ketchul Jesús Rodríguez-Viorato

(June 22nd, 2020)

Abstract

We give a Python program that is capable to compute and print all the distinct trivalent 2-stratifold graphs up to $N$ white vertices with trivial fundamental group (see [6]). Our algorithm uses the three basic operations described in [7] to construct new graphs from any set of given graphs. We iterate this process to construct all the desired graphs. The algorithm includes an optimization that reduces the repetition of generated graphs, this is done by recognizing equivalent white vertices of a graph under automorphism. We use a variation of the AHU algorithm to identify those vertices and as well to distinguish isomorphic graphs in linear time. The returned string from the AHU algorithm is also used as a hashing function to search for repeated graphs in amortized constant time.

1 Introduction

Since 2016, the authors José Carlos Gómez-Larrañaga, Francisco González-Acuña, and Wolfgang Heil have studied 2-stratifolds [5]. There are multiple motivations to follow their work, but one of the most interesting is the applications of the 2-stratifolds on the field of Topological Data Analysis.

The classification of 2-manifolds has been well studied, but the study of the 2-stratifolds has just started. On [7], Gómez-Larrañaga, González-Acuña, and Wolfgang started to analyze the ones with trivial fundamental group, giving a process to build them. And continuing with that work, it’s easy to ask how many of those exist.

Moreover, using the operations described in their work, we started to wonder if there was possible to use them to get every 2-stratifold. Yair Hernández, wrote a computational algorithm [8] to build some of them, and based on that code, we decided to extend it to get the 2-stratifolds meticulously; in an optimized way.

Since the operations described on [7] are performed on white vertices, it was decided to use the number of white vertices as a parameter for the algorithm, limiting the number of graphs that it was going to build. Therefore our program can calculate and draw the graph representation defined in [7] of every 2-stratifold with trivial fundamental group up to $N$ white vertices.

The code was written on Python and can be consulted on [1]. In order to identify different graphs, it used a modified version of the AHU algorithm. And to optimize the algorithm, there is defined an identification among white vertices under automorphisms of the graph (see def. 5.3). The modified version of the AHU algorithm, the algorithm 4, allows us to identify every graph with a unique string, which is the string representation, that is used as a hash to discard the repeated graphs and optimize the building process.

The contents of this paper include a description of the algorithm previously mentioned and the proof that it actually builds all the graphs that it is asked to. In section 2, there are given basic graph theory definitions, that are necessary to understand the proves. In section 3, there are proven some known results of graph isomorphisms but applied to the graph representations of the 2-stratifolds. In the next section,“Characterizing weighted trees with a string”, we describe the modified version of the AHU algorithm and we explain how it is helpful to solve the problem of classifying the trivalent graphs and therefore the 2-stratifolds with trivial fundamental group. In the section “The graph generator algorithm”, we describe the main algorithm that assigns a string representation to every graph, and we give the results of the construction of the graphs up to 11 white vertices, including a comparison between the optimized and non-optimized version. Finally, in “Nomenclature” we explained the tag that is given to every graph at the end of the algorithm because although the string representation is unique, it doesn’t work as a quick resume of the general shape of the graph.

2 Preamble

Definition 2.1.

We will say that a graph generated by a simply-connected trivalent 2-dimensional stratifold is a trivalent graph.

Definition 2.2.

Let be $G$ a graph, a set of vertices $\{v_{0},v_{1},...,v_{n}\}\subset G$ such that $v_{i}$ is adjacent to $v_{i+1}$ , and $v_{i}\neq v_{j}$ for every $0\leq i,j\leq n-1$ is called a path from $v_{0}$ to $v_{n}$ in $G$ .

Definition 2.3.

The degree of a vertex $v$ in a graph $G$ is the number of vertices in $G$ that are adjacent to $v$ . The set of all the vertices that are adjacent to $v$ are the neighbors of $v$ and we denote them by $N(v)$ . A vertex of degree 1 is a leaf.

Definition 2.4.

Given a $u-v$ path $R$ in $G$ the length of the path is the sum of the weights of the edges encountered in $R$ . For two vertices $u$ and $v$ , the shortest path is the $u-v$ path with minimum length, and the largest path is the $u-v$ path with maximum length. The length (without weights) of a path is the length of the path considering that all the weights are 1.

Definition 2.5.

Let $v$ be a vertex of a graph $G$ , its eccentricity $e(v)$ is the length (without weights) of the largest path from $v$ to another vertex in $G$ . The radius of $G$ , $rad(G)$ , is the smallest eccentricity among the vertices of $G$ . For any vertex $v$ , such that $e(v)=rad(G)$ we say that $v$ is a central vertex of $G$ , if $G$ has only one central vertex $u$ , we say that $u$ is the center of $G$ .

Definition 2.6.

Given a graph $G$ , we say that $G$ is a tree if and only if for every $v,w$ vertices of $G$ , there exists a path from $v$ to $w$ and there is no path with positive length from $v$ to itself. A rooted tree is a tree with a special vertex identified as the root.

Definition 2.7.

On a rooted tree, a vertex $v$ is a child of vertex $w$ if, in the path from the root to $v$ , $v$ immediately succeeds $w$ . We said that $w$ is parent of $v$ if and only if $v$ is child of $w$ .

3 Isomorphic graphs

Definition 3.1.

Two weighted graphs $G$ and $H$ are isomorphic if there exists a bijective function $\phi:V(G)\to V(H)$ such that two vertices $u$ and $v$ are adjacent in $G$ if and only if $\phi(u)$ and $\phi(v)$ are adjacent in $H$ , and for every edge, $u-v$ in $G$ , the edge $\phi(u)-\phi(v)$ in $H$ has the same weight as $u-v$ . If there is no such function $\phi$ as described above, the $G$ and $H$ are non-isomorphic graphs. (Definition from [4]) Moreover, for $G$ and $H$ rooted trees with roots $r_{G},r_{H}$ , respectively, we say that $G$ and $H$ are isomorphic as rooted trees if they are isomorphic and $\phi(r_{G})=r_{H}$ .

Lemma 3.1.

If two graphs $G$ and $H$ are isomorphic with a function $\phi:V(G)\to V(H)$ , for $u$ vertex of $G$ , $u$ is a leaf of $G$ if and only if $\phi(u)$ is a leaf of $H$ .

Proof.

Let $u$ a leaf of $G$ , then by definition, there exists only one vertex adjacent to $u$ in $G$ , suppose $v$ . As $u$ and $v$ are adjacent in $G$ , $\phi(u)$ and $\phi(v)$ are adjacent in $H$ . For any other $w$ vertex in $G$ , different from $u$ or $v$ ; $w$ is not adjacent to $u$ in $G$ and therefore $\phi(w)$ is not adjacent to $\phi(u)$ in $H$ . Then, $\phi(v)$ is the only vertex adjacent to $\phi(u)$ in $H$ , concluding that $\phi(u)$ must be a leaf of $H$ . Analogously if $\phi(u)$ is a leaf of $H$ we can conclude that $u$ must be a leaf of $G$ . ∎

Corollary 3.1.1.

If two graphs $G$ and $H$ are isomorphic, then they have the same number of leaves.

Definition 3.2.

Two trivalent graphs $G$ and $H$ are isomorphic as trivalent graphs if there is an isomorphism $\phi$ as weighted graphs such that, if $B(G),B(H)$ are the sets of black vertices of $G,H$ , and $W(G),W(H)$ are the sets of white vertices of $G,H$ , the functions $\phi\restriction_{B(G)}:B(G)\to B(H)$ and $\phi\restriction_{W(G)}:W(G)\to W(H)$ are bijective.

Lemma 3.2.

If two trivalent graphs $G$ and $H$ are isomorphic, then they have the same number of white and black vertices and the same number of leaves.

Proof.

If $G$ and $H$ are two trivalent graphs that are isomorphic, there exists $\phi:V(G)\to V(H)$ such that $\phi\restriction_{B(G)}:B(G)\to B(H)$ and $\phi\restriction_{W(G)}:W(G)\to W(H)$ are bijective, therefore $|B(G)|=|B(H)|$ and $|W(G)|=|W(H)|$ . And by corollary 3.1.1, $G$ and $H$ have the same number of leaves. ∎

Theorem 3.3 (Theorem 2.7 in [4]).

There exists a unique path between any two vertices of a tree.

Lemma 3.4.

For $G$ and $H$ two isomorphic trees with isomorphism function $\phi$ , for every two vertices $u$ , $v$ in $G$ , the length of the $u-v$ path in $G$ is the same as the length of the $\phi(u)-\phi(v)$ path in $H$ .

Proof.

Given that $G$ and $H$ are trees, by theorem 3.3 there exists a unique path between any two vertices in them. Let $u$ , $v$ be vertices in $G$ , there exists $R=\{u=r_{0},r_{1},...,r_{n-1},v=r_{n}\}$ a unique path between them, such that $R$ is a sequence of adjacent vertices without repetition in $G$ . For two adjacent vertices $a,b$ let’s denote $(a,b)$ as the length of the edge between them, then the length of $R$ is

length(R)=\sum_{i=0}^{n-1}(r_{i},r_{i+1})

First, notice that by the definition of path $r_{i}$ and $r_{i+1}$ are adjacent in $G$ , then $\phi(r_{i}),\phi(r_{i+1})$ are adjacent in $H$ , for every $i$ , $0\leq i\leq n-1$ . Also by definition of $R$ , $r_{i}\neq r_{j}$ for $i\neq j$ , and by definition of $\phi$ this implies that $\phi(r_{i})\neq\phi(r_{j})$ for $i\neq j$ .
Then $Q=\{\phi(u)=\phi(r_{0}),\phi(r_{1}),...,\phi(r_{n-1}),\phi(v)=\phi(r_{n})\}$ is a sequence of adjacent vertices without repetition in $H$ , which implies that $Q$ is a $\phi(u)-\phi(v)$ path, and since $H$ is a tree, $Q$ is the unique $\phi(u)-\phi(v)$ path in $H$ .
Finally, by definition of $\phi$ for every edge, $a-b$ in $G$ , the edge $\phi(a)-\phi(b)$ in $H$ has the same weight, therefore:

length(Q)=\sum_{i=0}^{n-1}(\phi(r_{i}),\phi(r_{i+1}))=\sum_{i=0}^{n-1}(r_{i},r_{i+1})=length(R)

∎

Corollary 3.4.1.

For $G$ and $H$ two isomorphic trees, their radius will have the same length.

Lemma 3.5.

Let $G$ and $H$ be two isomorphic trees with isomorphism function $\phi$ , for any $v$ vertex of $G$ , the function $\phi\mid_{N(v)}$ , where $N(v)$ is the set of the neighbors of $v$ , is a bijective function with codomain $N(\phi(v))$ in $H$ .

Proof.

Given $v$ a vertex of $G$ , let $x\in N(v)$ . That happens if and only if $length_{1}(v,x)=1$ . In the other hand, $\phi(x)$ is neighbor of $\phi(v)$ if and only if $length_{1}(\phi(v),\phi(x))=1$ . By using a particular case of the previous lemma we have that $length_{1}(v,x)=length_{1}(\phi(v),\phi(x))$ , therefore $x\in N(v)$ if and only if $\phi(x)\in N(\phi(v))$ . Since $\phi$ is a bijection then $\phi\mid_{N(v)}:N(v)\to N(\phi(v))$ is a bijection too. This means that the images of the neighbors of $v$ are the neighbors of the image of $v$ . ∎

Let’s denote $(a,b)_{p}$ as the path from $a$ to $b$ in the graph and $length_{1}(a,b)$ as its length (without weights), since all the graphs generated by the simply-connected trivalent 2-dimensional stratifolds are trees, by Theorem 3.3 this is well defined.

Lemma 3.6.

For any vertex $v$ in a tree $G$ , if $u$ is a vertex such that $length_{1}(u,v)=e(v)$ then $u$ is a leaf.

Proof.

Suppose that $u$ is not a leaf, then the degree of $u$ is at least $2$ , then there exists $x$ neighbor of $u$ such that $x\not\in(v,u)_{p}$ . By theorem 3.3 we know that such $x$ exists, because there is a unique path from $v$ to $u$ which means that there is only one neighbor of $u$ connected to $v$ . If there where $x,y$ neighbors of $u$ connected to $v$ , there would be two paths from $v$ to $u$ and that is a contradiction.
Let’s notice that the

e(v)=length_{1}(v,u)<length_{1}(v,u)+1=length_{1}(v,u)+length_{1}(u,x)=length_{1}(v,x),

but that’s a contradiction to the definition of eccentricity. Therefore the degree of $u$ must be at most 1, and $u$ is a leaf of $G$ . ∎

Theorem 3.7 (Uniqueness of the center).

Let $G$ be a trivalent graph, then there exists $c$ center of $G$ and it is unique.

Proof.

By definition, there exists at least one vertex $v$ such that $e(v)=rad(G)$ .
First, let’s notice that two vertices of different colors in a trivalent graph can’t be both central vertices. Every trivalent graph has the property that all the neighbors of a white vertex are black vertices and vice versa, also all the leaves are white. Then by parity, the $length_{1}$ from any white vertex to a leaf would be even and the $length_{1}$ from any black vertex to a leaf would be odd, using the lemma 3.6 we can conclude that the eccentricity of a white vertex would be always different from the eccentricity of a black vertex, which means that they can’t be both central vertices.
Now suppose that there exists $u\neq v$ such that $u$ is a central vertex of $G$ . Without loss of generality we can assume that $u,v$ are both white. Then there exists $x$ a black vertex such that $x\in(u,v)_{p}$ . We would prove that $e(x)<e(v)$ .
Let $l_{1},l_{2},....,l_{n}$ be the leaves of $G$ , by definition, for any leaf $l_{i}\in G$ , we will have $length_{1}(v,l_{i})\leq e(v)$ and $length_{1}(u,l_{i})\leq e(u)$ .
Notice that for any $l_{i}$ we have two options, $x\not\in(v,l_{i})_{p}$ or $x\in(v,l_{i})_{p}$ . We will analyze both cases.
Case 1, $x\not\in(v,l_{i})_{p}$ :
If $x\not\in(v,l_{i})_{p}$ , in particular $(x,u)_{p}\not\subset(v,l_{i})_{p}$ because $x\in(x,u)_{p}\subset(v,u)_{p}$ and the last one is unique, by lemma 3.3. Notice that there exists a unique vertex $w\in(v,x)_{p}$ (it could happen that $w=v$ ) such that $(v,l_{i})_{p}=(v,w)_{p}\cup(w,l_{i})_{p}$ and $(w,l_{i})_{p}\cap(v,x)_{p}=\{w\}$ , therefore we have that

length_{1}(w,l_{i})+length_{1}(x,w)=length_{1}(x,l_{i})<length_{1}(x,l_{i})+length_{1}(u,x)=length_{1}(u,l_{i})\leq e(u)=e(v)

Then $length_{1}(x,l_{i})<e(v)$ .
Case 2, $x\in(v,l_{i})_{p}$ :
Since $x\in(v,l_{i})_{p}$ then $(v,l_{i})_{p}=(v,x)_{p}\cup(x,l_{i})_{p}$ therefore

length_{1}(x,l_{i})<length_{1}(x,l_{i})+length_{1}(v,x)=length_{1}(v,l_{i})\leq e(v)

which implies $length_{1}(x,l_{i})<e(v)$ .
From both cases, we can conclude that $length_{1}(x,l_{i})<e(v)$ for any leaf $l_{i}\in G$ , then

\displaystyle e(x)=\max_{1\leq i\leq n}length_{1}(x,l_{i})<e(v),

contradicting the fact that $v$ and $u$ were both central vertices because there is another vertex with lower eccentricity than the radius.
This proves that for any trivalent graph, the center exists and it is unique. ∎

Lemma 3.8.

Any two trivalent graphs are isomorphic as trivalent graphs if and only if they are isomorphic as graphs.

Proof.

By definition, it is clear that isomorphism as trivalent graphs implies isomorphism. We only need to prove that isomorphism implies isomorphism as trivalent graphs, which is the isomorphism function determines a bijection between the set of black vertices of both graphs, analogously with the white vertices.
Let $G$ and $H$ be two trivalent graphs. If instead of the length in lemma 3.4 we consider the length (without weights) we can conclude that for any vertex $v\in G$ , if $\phi(v)=w\in H$ then $e(v)=e(w)$ .
Using the same parity argument as in the previous proof, notice that $e(v)=e(w)$ if only if $v,w$ are both white or both black. Moreover, $e(v),e(w)$ would be odd if and only if $v$ and $w$ are black, and would be even if and only if $v$ and $w$ are white.
This gives us a partition of the graph that assures us that the image of any white vertex is going to be a white vertex, and the image of any black vertex is going to be a black vertex. Therefore the restriction of $\phi$ to the set of black vertices in $G$ is a bijection with codomain the set of black vertices in $H$ , analogously with the white vertices. Then we can conclude that isomorphism implies isomorphism as trivalent graphs. ∎

Lemma 3.9.

For $G$ and $H$ two isomorphic trivalent graphs with isomorphism function $\phi$ , then the center of $H$ is the image of the center of $G$ under $\phi$ .

Proof.

As a result of the lemma 3.4, if we consider the length (without weights) instead of the length, for any $v\in G$ , the eccentricity of $v$ in $G$ will be the same as the eccentricity of $\phi(v)$ in $H$ . Let $c$ be the center of $G$ , which is unique, using corollary 3.4.1 we have that

rad(H)=rad(G)=e(v)=e(\phi(c))

By definition, since $rad(H)=e(\phi(c))$ we can conclude that $\phi(c)$ is the center of $H$ . ∎

Lemma 3.10.

Given $G$ and $H$ trivalent graphs, if we select the center of each graph as its root, $G$ and $H$ are isomorphic as trivalent graphs if and only if $G$ and $H$ are isomorphic as rooted trees.

Proof.

If $G$ and $H$ are isomorphic as trivalent graphs, by lemma 3.9, since the center of $H$ is the image of $G$ under the isomorphism function, it is immediate that $G$ and $H$ are isomorphic as rooted trees. Now let’s suppose that $G$ and $H$ are isomorphic as rooted trees. By definition, the isomorphism as rooted trees implies that $G$ and $H$ are isomorphic, therefore by lemma 3.10, since $G$ and $H$ are two trivalent graphs that are isomorphic, then they are isomorphic as trivalent graphs. ∎

4 Characterizing weighted trees with a string

So far, we have described how two isomorphic trivalent graphs behave, but we need tools to identify if two trivalent graphs are isomorphic. This is important because the main goal is to know how many and which are all the trivalent stratifolds for a given number of white vertices. Since the trivalent stratifolds are associated with a unique trivalent graph, having a classification for the trivalent graphs gives us a classification for the trivalent stratifolds.

The generation of all the trivalent graphs is an iterative process that creates a lot of isomorphic graphs, we will discuss this process further in Section 6. But it is because of this excess of repetitions, that we need an optimal algorithm that can recognize isomorphic graphs with as few operations as possible.

In the book The Design and Analysis of Computer Algorithms [2] the authors propose an algorithm that allows us to identify if two non-weighted rooted trees are isomorphic in $O(n)$ time. This algorithm is known as the AHU algorithm, the acronyms AHU comes from the initials of the authors Aho, Hopcroft, and Ullman. To use this algorithm is necessary to remark that two isomorphic trees could be non-isomorphic as rooted trees (see Fig. 1 for an example).

Refer to caption — Figure 1: This is an example of two isomorphic trees that aren’t isomorphic as rooted trees. On each tree, we have marked in bold black the root.

In the article Tree isomorphism Algorithms: Speed vs. Clarity [3], there is an algorithm that improves the idea of Aho, Hopcroft, and Ullman, by implementing the use of parenthetical tuples. And then substituting the use of ‘(’, ‘)’ for ‘1’ and ‘0’ respectively, the latest have a natural order.

Given a rooted tree $T$ , the main idea of the algorithm is to assign a unique string to each vertex of $T$ recursively. The string assigned to a vertex is created recursively from the string associated with its children. And finally, assign to $T$ the string associated with its root. Then we can conclude that two rooted trees are isomorphic if and only if they have the same associated string.

We now present the pseudo-code of the AHU Algorithm. An example of this process can be seen in Fig. 2.

Algorithm 1 AHU(

v

: vertex)

v

is childless then

Give

v

the tuple name “10”

return “10”

else

Set

L=\emptyset

for all

w

child of

v

tag

= AHU(

w

);

Append

tag

L

end for

Sort

L

using binary order

Set

temp=

Concatenation of tags in

L

Give

v

the tuple name “

1temp0

”

end if

Although this algorithm allows us to recognize if two rooted trees are isomorphic, it doesn’t allow us to distinguish if two rooted trees with weights are isomorphic, because it doesn’t take into account the weights. Since trivalent graphs are weighted trees, this algorithm doesn’t work for our problem in the first instance.

By theorem 3.7, given a trivalent graph $G$ , there is a unique vertex $v$ such that $v$ is the central vertex of $G$ , we call $v$ the center of $G$ . The uniqueness of the center for every trivalent graph allows us to mark this vertex as the root of the trivalent graph, without ambiguity.

We have proven that the center exists, but so far we only have given an exhaustive algorithm to find it. In [2] on pages 176 to 179, Aho, Hopcroft, and Ullman describe the algorithm Depth-first search whose purpose is to find the largest path in a tree. It is proven that this algorithm only needs $O(\max\{n,e\})$ steps on a graph with $n$ vertices and $e$ edges. The idea of this algorithm is to visit every vertex of the tree in an ordered way, going deeper before continuing to another branch of the tree, this way we can assure that we visit every vertex exactly once.

Algorithm 2 Depth-first_search(

v

:vertex)

v

is childless then

return

{v}

else

Set

length=0

and

longestPath=\emptyset

for all

w

child of

v

Set

path=

Depth-first_search(

w

) and

L

as the length of

path

L>length

then

Set

length=L

and

longestPath=path

end if

end for

return

{v}\cup longestPath

end if

To find the center of the trivalent graph it is only necessary to find the longest path in the tree and then find the middle vertex of it. This will always be the center of the tree. The pseudo-code is the algorithm 3.

The Algorithm 3 successfully finds the center of any trivalent graph because it first finds a path of maximal length (a diameter) of the tree. Any diameter of a trivalent has an even length (see Theorem 3.7 ). By the definition of the center, all vertices must be at a distance at most half of the diameter. That is why the center must be in the middle of any diameter.

Algorithm 3 center(

G

: Trivalent graph)

Set

v

a vertex of

G

Set

longestPath=

Depth-first_search(

v

)

Set

w

as the last vertex of the path

longestPath

Set

longestPath=

Depth-first_search(

w

)

Set

center

as the middle vertex of

longestPath

return

center

To prove that we can find a diameter with two runs of DFS we do as follows. What we have to show is that at the first run of the DFS we end up at the end of a diameter of $G$ . So, at the next run, we will end up at the other end of the diameter. Then, what we have to show is that that farthest vertex $w$ from a given vertex $v$ in $G$ belongs to a diameter of $G$ .

Let $w$ be one of the farthest vertices from $v$ . Observe first that $w$ has to be a leaf, otherwise, we can find a farther vertex from $v$ . Now, let $\gamma$ a diametrical path of $G$ . As $w$ is a leaf, if $w$ belongs to $\gamma$ then the proof would be over. Lets call $a$ and $b$ the ends of $\gamma$ . By the definition of $w$ , the vertices $a$ and $b$ need to be no further from $v$ than $w$ . If one of them were closer to $v$ , we can prove that one of the paths from $w$ to $a$ or $b$ is longer than $\gamma$ (an analysis by cases is needed it here). This contradicts the fact that $\gamma$ is a diameter. Similarly, if both $a$ and $b$ are as far from $v$ than $w$ , it implies that one of the paths from $w$ to $a$ or $b$ is as long as $\gamma$ , making $w$ the end of a diameter. Which completes the proof. So, the second time that the DFS runs, it will find the other end of the diameter.

This algorithm needs twice the number of steps that Deep-first_search plus a constant, which means that this algorithm is still linear and only depends on the number of vertices and edges of the graph.

Now, every trivalent graph can be seen as a rooted tree and therefore we can apply the AHU algorithm to it. The problem is that the AHU algorithm doesn’t take into account the weights of the edges, but we have solved this problem by instead of assigning only numbers ‘1’ and ‘0’ we include the numbers ‘2’ and ‘3’ depending on the weight in the edge that connects the vertex with its father. This algorithm still runs on linear time.

The recursive part of the algorithm is given by the following pseudo-code:

Algorithm 4 AHU-modified(

v

:vertex)

v

is childless then

v

has no father or

Weight[v,father(v)]=1

then

Give

v

the tuple name “01”;

else

Give

v

the tuple name “23”;

end if

return The tuple name of

v

else

Set

L=\emptyset

for all

w

child of

v

tag

= AHU-modified(

w

);

Append

tag

L

end for

Sort

L

using base four order

Set

temp=

Concatenation of tags in

L

v

has no father or

Weight[v,father(v)]=1

then

Give

v

the tuple name “

0temp1

”;

else

Give

v

the tuple name “

2temp3

”;

end if

return The tuple name of

v

end if

Now, given any trivalent graph, to get its string it is necessary to get its center first and then get the string associated with that vertex. For the complete implementation, see Algorithm 5.

Algorithm 5 TG_to_string(

G

: Trivalent graph)

Set

c

as the output of center(

G

);

Set

c

as the root of

G

Vertex_to_string(

c

);

Return the tuple name of

c

;

Definition 4.1.

Given a trivalent graph $G$ we call the output of TG_to_string ( $G$ ) [5] as the string representation of $G$ .

Theorem 4.1.

Given two trivalent graphs, they are isomorphic if and only if they have the same string representation.

To prove this theorem, we are going to give an algorithm that recovers the original graph given a string, and this will prove that there is a unique graph associated with any string.

Algorithm 6 String_to_TG(

S

: string,

father

: vertex)

father

is NONE then

Draw a vertex

v

;

State

father

v

;

end if

if The first element of

S

is 0 then

Set

Close

as 1;

else

Set

Close

as 3;

end if

Set

i

as 2

while The

i

-th element of

S

is different from

Close

if The

i

-th element of

S

is 0 then

Draw a vertex

w

connected to

father

with weight 1;

else

Draw a vertex

w

connected to

father

with weight 2;

end if

Set

P

as the string

S

without its first element;

Set

i

= String_to_TG(

P

w

) + 2;

end while

Return

i

;

This algorithm draws a unique trivalent graph given a string representation, therefore we are giving a bijection between the trivalent graphs and the string representations, proving the theorem 4.1.

This algorithm can be extended for n-colored trees in general, also it can be extended for trees with a greater amount of weights, it only needed to add more start-close indicator numbers to identify the different weights.

5 The graph generator algorithm

Given a tivalent graph, one can generate more by applying the operations O1 or O2 to any white vertex of it. Or given two trivalent graphs, we can generate a new one by applying the operation O1* in one white vertex of each graph. It is proven in [7] that all the trivalent graphs can be obtained by recursively using these operations in all the previous trivalent graphs, starting with the B111 and B12 trees.

The B111 and B12 trees are defined in [7] in Definition 1.

Definition 5.1.

1.

The B111-tree is the bi-colored tree consisting of one black vertex incident to three edges each of label 1 and three terminal white vertices each of genus 0.
2.

The B12-tree is the bi-colored tree consisting of one black vertex incident to two edges one of label 1, the other of label 2, and two terminal white vertices each of genus 0.

Also the operations O1, O2 and O1* are defined in [7].

Definition 5.2.

In a trivalent graph $\Gamma$ let $w$ be a white vertex and let $e_{1},...,e_{m}$ be the edges incident to $w$ ( $m\geq 0$ ) and let $b_{i}$ be the black vertex incident to $e_{i}$ ( $i=1,...,m$ ). We define the operations $O1$ and $O2$ on $\Gamma$ that changes $\Gamma$ to a new trivalent graph $\Gamma_{1}$ as follows:

1.

O1. Let $0\leq k\leq m$ . Attach one white vertex of a B111-tree to $w$ , cut off $b_{k-1},...,b_{m}$ from $w$ and attach $b_{k+1},...,b_{m}$ to another white vertex of the B111-tree.
2.

O2. Attach a B12-tree to $w$ so that the terminal edge has label 1.
3.

O1*. On the other hand, let $\Gamma_{1}$ and $\Gamma_{2}$ be two disjoint trivalent graphs and let $w_{i}$ be a white vertex of $\Gamma_{i}$ ( $i=1,2$ ). Attach a B111-tree to $\Gamma_{1}\cup\Gamma_{2}$ so that $w_{1}$ and $w_{2}$ are identified with two distinct white vertices of the B111-tree.

To get all the trivalent graphs with $n$ white vertices, we have implemented a program that has two fundamental parts. The first part constructs all the trivalent graphs with $i$ white vertices ( $2\leq i\leq n$ ) and the second part reduces the list by eliminating the repetitions.

Algorithm 7 Construct_TG(

m

:integer)

Create

Complete\_list

a list with

m-1

empty lists;

Set the B12-tree as the first element of

Complete\_list[0]

;

Set the B111-tree as the first element of

Complete\_list[1]

;

for all

w

white vertex of B12-tree do

Set

\Gamma

as the rif the graph is already there. Here is when we have to use the Characterizing string from ing O2 to

w

;

Add

\Gamma

Complete\_list[1]

;

end for

for

n

[4,n]

for all

q

graph in

Complete\_list[n-3]

for all

w

white vertex of

g

Set

\Gamma

as the result of applying O2 to

g

in the vertex

w

Add

\Gamma

Complete\_list[n-1]

if it not already there.

end for

for all

g

graph in

Complete\_list[n-4]

for all

w

white vertex of

g

Set

\Gamma

as the result of applying O1 to

g

in the vertex

w

Add

\Gamma

Complete\_list[n-1]

if it not already there.

end for

for

i

[0,n-1]

n-i-5\geq 0

then

for all pair

(u,v)

where

u

is a white vertex of a graph in

Complete\_list[i]

v

is a white vertex of a graph in

Complete\_list[n-i-5]

Set

\Gamma

as the output of applying

O1^{*}

using the vertices

u,v

;

Add

\Gamma

Complete\_list[n-1]

if it not already there.

end for

end if

end for

We should mention that whenever we add a graph to $Complete\_list[n-1]$ we have to check if the graph is already there. Here is when we have to use the string representation of its elements (see Def. 4.1) to compare them. Even more, we can set the string representation as a hashing function, so we don’t have to iterate over all the elements of $Complete\_list[n-1]$ to decide if it already there or not, and decide it in amortized constant time. The complete implementation can be found in the repository https://github.com/MyHerket/TrivalentStratifold in GitHub.

As explained before, the creation of a new trivalent graph is an iterative process. And we are going to prove that the previous algorithm creates all the trivalent graphs with $n$ white vertices.

Lemma 5.1.

Let $G$ be a trivalent graph, there exists at least one leaf $w$ of $G$ such that the weight of the adjacent edge to $w$ is 1.

Proof.

We are going to proceed by induction. First, notice that for $b12-$ and $b111-tree$ there exists $w$ a leaf such that the weight of the adjacent edge to $w$ is 1.
Let $G$ be a trivalent graph, if we perform $O1$ in one of its vertices, we are attaching a $b111-tree$ by one of its white vertices, letting 2 white vertices free that are going to be leaves of $G$ with such that the weight of the adjacent edges to them is 1.
On the other hand, if we perform $O2$ in one of $G$ ’s vertices, we are attaching a $b12-tree$ to it by the only white vertex whose adjacent edge weight is 2, therefore the white vertex whose adjacent edge weight is 1, is now a leaf of the new graph
Finally, if we perform $O1^{*}$ to $G$ and other graph, by definition we take a $b111-tree$ and attach one white vertex to $G$ , one to the other graph and the last one is free, which is the leaf whose adjacent edge weight is 1.
Since the process to get any trivalent graph is taking $b12$ or $b111$ and performing $O1,O2$ or $O1^{*}$ , as many times as we want in each step we have a leaf whose adjacent edge weight is 1, therefore the resulting trivalent graph has it. ∎

Remark.

Let $G$ be a trivalent graph with $k$ white vertices, the resulting trivalent graph $G^{\prime}$ after performing $O1$ in any white vertex of $G$ has $k+2$ white vertices.

Remark.

Let $G$ be a trivalent graph with $k$ white vertices, the resulting trivalent graph $G^{\prime}$ after performing $O2$ in any white vertex of $G$ has $k+1$ white vertices.

Remark.

Let $G$ and $G^{\prime}$ be trivalent graphs with $k$ and $j$ white vertices, respectively. The resulting graph $H$ after performing $O1^{*}$ in any pair of white vertices of $G$ and $G^{\prime}$ has $k+j+1$ white nodes.

Using the previous remarks we have the following theorem:

Theorem 5.2.

For any $n$ an integer greater than 3. The list of all the trivalent graphs with $n$ white vertices, (including isomorphisms) will be obtained by performing the operation $O1$ to all the trivalent graphs with $n-2$ white vertices in each of their white vertices, performing the operation $O2$ to all the trivalent graphs with $n-1$ white nodes in each of their vertices and finally for every $m$ , such that $2\leq m\leq n-3$ perform the operation $O1^{*}$ in all the pairs of white vertices of every pair of trivalent graphs where the first one is an element of the list of trivalent graphs with $m$ white vertices and the second one is an element of the list of trivalent graphs with $n-m-1$ white vertices.

Proof.

Let $n$ be an integer greater than 3. By the remarks, it is clear that performing the algorithm described will give us a subset of the list of all the trivalent graphs with $n$ white vertices. Let’s see that this subset is the total set.
Let $G$ be a trivalent graph with $n>3$ white vertices and $w$ a leaf of $G$ such that the edge adjacent to $w$ has weight 1, it exists by lemma 5.1. We know that $w$ is a white vertex, by theorem 1 in [7]. Let $b$ be the black node adjacent to $w$ . If $b$ has degree 2, let $v$ be the other vertex adjacent to $b$ , when we erase the vertices $w,b$ we get a new graph $G^{\prime}$ with $n-1$ white vertices such that after performing $O2$ in $G^{\prime}$ in the vertex $v$ we get $G$ .
If $b$ has degree 3, then $b$ is part of a $b111-subtree$ , and let $v_{1}$ and $v_{2}$ the vertices adjacent to $b$ different to $w$ . If there is $v_{i}$ ( $i\in{1,2}$ ) such that its degree is one, suppose $v_{1}$ , when we erase the vertices $w,b,v_{1}$ , we get a new trivalent graph $G^{\prime}$ with $n-2$ white vertices such that after performing $O1$ in $v_{2}$ we get the original trivalent graph $G$ . On the other hand when neither $v_{1}$ nor $v_{2}$ has degree 1, when we erase the vertices $b,w$ we get two trivalent graphs $H$ and $H^{\prime}$ such that the sum of their white vertices is $n-1$ and after performing $O1^{*}$ in $v_{1},v_{2}$ we get the original graph $G$ .
Therefore every trivalent graph of the list was a result of a step in the algorithm described in the theorem and the algorithm gives us all the graphs, including isomorphisms.
∎

$n$	Total	Created
2	1	1
3	3	3
4	6	11
5	18	37
6	51	150
7	167	573
8	551	2267
9	1954	8997
10	7066	36498
11	26486	149708

Table 1: Number of distinct graphs we got for each value

n

(the number of white vertices), and the number of graphs that were created to construct them all.

This process is exhaustive, we can assure that it creates all the trivalent graphs with $n$ white vertices, but it creates too many repetitions. This is because there are symmetries in the rooted trivalent graphs, and when applying any operation in two symmetric vertices the resulting trivalent graph is the same.

Definition 5.3.

Given $G$ a rooted trivalent graph, we say that two vertices $u,v\in G$ are symmetric if there exists an automorphism $\phi:G\to G$ (as rooted weighted graphs) such that $\phi(u)=v$ .

It is clear that if two vertices are symmetric, they must have the same string representation because the string representation of a vertex $v$ depends solely on the isomorphisms class of the subtree defined by the descendants of $v$ . Unfortunately, having the same string representation is not enough to recognize symmetric vertices. The fathers of two symmetrical vertices $u$ and $v$ must be symmetrical as well ( an automorphism $\phi:G\to G$ must send the father of $u$ to the father of $v$ ). This implies, that the process of detecting symmetrical vertices can be iterated recursively, and it will end when the fathers of two vertices coincide (when they are siblings).

We use the above idea for detecting symmetric white vertices of a graph $G$ . And we modified algorithm 7 to work only with symmetrically distinct white vertices. These changes reduced the number of generated graphs by around $20\%$ as shown in Table 2.

$n$	Created	Reduction
4	11	0,00%
5	32	13,51%
6	122	18,67%
7	467	18,50%
8	1781	21,44%
9	7099	21,10%
10	28852	20,95%
11	119168	20,40%

Table 2: Number of created graphs after considering symmetrically distinct white vertices.

More optimization could’ve been done to avoid so many repetitions, but the program would’ve run in exponential time anyway. Because the number of graphs we want to construct has exponential growth.

6 Nomenclature

We need a nomenclature to differentiate the trivalent graphs. For $G$ a trivalent graph, the tag is going to be the identifier of $G$ . To have a general idea of the shape of the graph it is necessary to include the number of leaves, black and white nodes. Also, we will include the length of the largest and shortest leaf paths of $G$ . And an ID number that identifies $G$ as a unique graph.
Denote $W(G),B(G),L(G)$ the sets of white vertices, black vertices and leaves of $G$ , respectively.
The tag will have the following structure:

$tag(G)$ = [ $|W(G)|$ , $|B(G)|$ , $|L(G)|$ , length(shortest leaf path), length(largest leaf path), ID number]

The $ID$ number is automatically generated by the program when using the Hash table that uses the unique string representation of $G$ to order it in the list of trivalent graphs.

References

[1] Trivalent stratifold repository.
[2] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The design and analysis of computer algorithms. Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing, Addison-Wesley Series in Computer Science and Information Processing.
[3] Douglas M. Campbell and David Radford. Tree isomorphism algorithms: speed vs. clarity. Math. Mag., 64(4):252–261, 1991.
[4] Gary Chartrand and Ping Zhang. Chromatic graph theory. Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL, 2009.
[5] J. C. Gómez-Larrañaga, F. González-Acuña, and Wolfgang Heil. 2-dimensional stratifolds. In A mathematical tribute to Professor José María Montesinos Amilibia, pages 395–405. Dep. Geom. Topol. Fac. Cien. Mat. UCM, Madrid, 2016.
[6] J. C. Gomez-Larrañaga, F. González-Acuña, and Wolfgang Heil. Classification of simply-connected trivalent 2-dimensional stratifolds. Topology Proc., 52:329–340, 2018.
[7] J. C. Gomez-Larrañaga, F. González-Acuña, and Wolfgang Heil. Models of simply-connected trivalent 2-dimensional stratifolds. Bol. Soc. Mat. Mex., 26:1301––1312, 2020.
[8] Hernández Yair. Stratifolds. https://github.com/yair-hdz/stratifolds, 2018.