{'fraction_non_alphanumeric': 0.04069903823598405, 'fraction_numerical': 0.015912111971225273, 'mean_word_length': 3.8089866516262454, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Honeycomb Toroidal Graphs

Honeycomb toroidal graphs are trivalent Cayley graphs on generalized dihedral groups. We examine the two historical threads leading to these graphs, some of the properties that have been established, and some open problems.


Introduction
This paper discusses a family of graphs called honeycomb toroidal graphs. They have arisen in two distinct settings which are discussed in the next two sections. This is followed by an examination of some of their properties and some parameters of interest. Several open problems also are mentioned.
Given the disparate subject areas employing graphs as models, there are a variety of concepts for which different terms are used across disciplines. Thus, we shall mention some terminolgy used in this paper. A graph has neither loops nor multiple edges. The valency of a vertex v, denoted val(v), is the number of edges incident with u. The order of a graph is the cardinality of its vertex set and the size of a graph is the cardinality of its edge set.
1.1 Definition. Let G be a finite group and S ⊂ G satisfying 1 ∈ S and s ∈ S if and only if s −1 ∈ S. The Cayley graph on G with connection set S, denoted Cay(G; S), has the elements of G as its vertex set and has an edge joining g and h if and only if h = gs for some s ∈ S.
A path of length in a graph is a subgraph consisting of a sequence v 0 , v 1 , . . . , v of + 1 distinct vertices such that the edge v i v i+1 belongs to the path for i = 0, 1, . . . , − 1. A cycle of length is a connected subgraph of size in which every vertex has valency 2. Cycles are denoted by a sequence of vertices as they occur along the cycle with the convention that the first vertex and the last vertex of the sequence are the same in order to distinguish it from a path. A Hamilton cycle in a graph is a cycle containing every vertex of the graph, and a Hamilton path is a path containing every vertex.

Algebraic And Topological Viewpoint
Altshuler [5] considered three families of equivelar maps on the torus and was able to show that every graph in two of the families possesses a Hamilton cycle, but was unable to do so for the other family. The latter family consists of the equivelar maps with Schläfli type (6,3), that is, the boundaries of all the faces are 6-cycles and vertices all have valency 3. Many of these graphs, but not all, are Cayley graphs on the appropriate dihedral group. So this problem arising in topological graph theory impinges on another problem which has drawn considerable attention for fifty years, namely, does every connected Cayley graph of order at least three have a Hamilton cycle?
The answer to the preceding question for Cayley graphs on abelian groups was known to be yes as early as the first edition of Lovász's book entitled Combinatorial Problems and Exercises [12]. However, a much stronger result by Chen and Quimpo [7] appeared in 1981. Their theorem follows two definitions. A graph X is Hamilton-connected if for every pair of vertices u and v in X there is a Hamilton path whose terminal vertices are u and v. A bipartite graph X is Hamilton-laceable if the same property holds for any two vertices in opposite parts.
2.1 Theorem. If X is a connected Cayley graph of valency at least 3 on an abelian group, then X is Hamilton-connected unless it is bipartite in which case it is Hamilton-laceable.
Note that the preceding theorem implies that every edge of a connected Cayley graph on an abelian group belongs to a Hamilton cycle. If the valency is at least 3, it is implied by the theorem. If the valency is 2, the graph is a Hamilton cycle.
The dihedral group is close to being abelian in the sense that the dihedral group D n of order 2n contains an abelian subgroup of index 2, that is, has order n. In fact, it still is not known whether every connected Cayley graph on D n is hamiltonian in spite of the efforts of a non-trivial number of people working on the problem for the last forty plus years.
As we shall see soon, when considering Cayley graphs on dihedral groups, those for which the connection set consists of three reflections turn out to be crucial. Let's now take a closer look at these particular graphs.
Throughout this paper we let D n denote the dihedral group of degree n and order 2n. We visualize the group as the symmetries of a regular n-gon. So the group is generated by an element ρ of order n (it rotates the n-gon cyclically) and a reflection τ . Thus, |τ | = 2 and τ ρτ = ρ −1 . The cyclic subgroup ρ has index 2 in D n . Note that the coset ρ τ consists of n reflections. When n is odd, the n reflections are the only involutions in D n , whereas, ρ n/2 also is an involution when n is even.
We are interested in Cayley graphs on D n whose connection sets consist of three reflections. Let S = {ρ i τ, ρ j τ, ρ k τ }, where 0 ≤ i < j < k < n. It is clear that the connection set {τ, ρ j−i τ, ρ k−i τ } produces an isomorphic Cayley graph. Hence, we shall assume the connection set has the form The graph X = Cay(D n ; S)) is connected if and only if it is the case that gcd(n, i, j) = 1. So dealing with connectivity is straightforward. The subgraph generated using just τ and ρ i τ consists of m cycles of length 2n/m, where m = gcd(n, i). The case in which we are most interested is when m > 1 and X is connected. This means that the element ρ j τ generates edges that connect the m cycles to form a single component for X. We want to take a careful look at these graphs to see how to represent them nicely.
The vertices of ρ are cyclically labelled 1, ρ, ρ 2 , . . . , ρ n−1 and those of ρ τ are cyclically labelled τ, ρτ, ρ 2 τ, . . . , ρ n−1 τ . The m cycles have the properties that they have even length at least 4, and the vertices alternate between belonging to ρ and ρ τ . Let ρ j τ generate an edge joining a vertex of ρ in a cycle C 1 to a vertex of ρ τ in another cycle C 2 . The distance (under the cyclic labellings) to the next element of ρ along C 1 is the same as the distance to the next element of ρ τ along C 2 . Hence, these two vertices also are joined by an edge generated by ρ j τ . This is true for all the edges generated by ρ j τ joining the cycles together.
Therefore, we may label the vertices of the graph as u i,j , 0 ≤ i ≤ m − 1 and 0 ≤ j ≤ n − 1 so that the following are the edges: • u i,j u i,j+1 for i = 0, 1, . . . , m − 1 and j = 0, 1, . . . , n − 1, where the second subscript is reduced modulo n (these are called vertical edges); • u i,j u i+1,j for i = 0, 1, . . . , m − 2 and all j such that i + j is odd (these are called flat edges; and • u m−1,j u 0,j+ , where m, j, all have the same parity (these are called jump edges. As we label the columns from left to right, it is clear that we may assure that the edges between successive columns are flat. However, once the last column is labelled the only feature we know about the edges from the last column back to the first column is that they have the same change in the second coordinate, that is, they have the same jump. We now have a straightforward description of these graphs. They are called honeycomb toroidal graphs and are denoted HTG(m, n, ), where m is the number of column cycles, n is the length of the column cycles so that n ≥ 4 and is even, and is the jump from the last column back to the first.  Figure 1 demonstrates clearly how HTG(m, n, ) may be embedded on a torus for any choice of the parameters. Even though these graphs all have nice embeddings on the torus, they are slightly misnamed in that they are not all toroidal graphs. This turn of events comes about because in order for a graph that embeds on the torus to be toroidal it must be non-planar.
The graphs HTG(2, n, 0), for all even n ≥ 4, and HTG (2,4,2) are, in fact, planar graphs. All others are non-planar. Nevertheless, we shall refer to all graphs in the family as honeycomb toroidal graphs

Network Topology Viewpoint
Network topology refers to methods used to connect objects together to perform certain tasks. For example, connecting computers together to form a computer network or connecting processors within a single computer fall within the area. Some desirable properties are small valency so that the number of direct connections is not too big and symmetry meaning that all the vertices are essentially the same which allows local algorithms to be the same at each vertex.
One approach is to start with tesselations of the plane by regular polygons. These have an infinite number of vertices so that some modifications are required. One such modification is to bound a finite region of a tesselation with a "nice polygon" to obtain a finite graph. The latter graph is called a mesh. The mesh is not regular but the addition of a few edges may result in a graph that is not only regular but also is vertex-transitive.
The tesselation of the plane by regular hexagons is one source for which this was done. Stojmenovic [17] suggested three bounding types of polygons to obtain meshes: a hexagonal polygon, a square polygon and a rhombic polygon. He then determined ways to add edges so that all vertices have valency 3 and the resulting graph is vertex-transitive.  shows the three smallest graphs obtained by Stojmenovic using a hexagonal bounding polygon. We need to examine the viewpoint in some detail because this formed the foundation for the way subsequent researchers in the area developed the ideas. He called the graph in Figure 2(a) a hexagonal torus of size 1. The graph in Figure 2(b) he called the hexagonal torus of size 2. Thus, to increase the size by 1 we add a ring of hexagons around the current graph. This is a very geometric way of building the graphs.
His use of a square as a bounding polygon has since been extended to using a rectangle, and his use of a rhombus for a bounding polynomial has been extended to using a parallelogram. All three types of graphs share the property that they arise geometrically. They are, in fact, very special honeycomb toroidal graphs as domonstrated in the next result.
Some comments about terminology are in order. Because of the way the network topology approach developed these graphs, they were understandably viewed as special. Thus, when it was discovered [9] how to broaden the construction, the term generalized honeycomb torus was adapted and appears in many papers. However, we object to this terminology for two reasons leading to the term honeycomb toroidal graph being used.
The first objection is because the torus is a closed orientable surface of genus one and even though these graphs have nice embeddings on the torus, the graphs themselves should not be called tori. The second objection arises because we have seen that the only differences between them come from changing three descriptive parameters. There is no particular set of parameters that is special and the term 'generalized' is inappropriate.
The answer to the first question is yes and was proven in [20]. We give a short proof of this result but before doing so we discuss a useful constructive technique for honeycomb toroidal graphs.
Consider a graph with vertex set {u i,j : 0 ≤ i ≤ 2 and 0 ≤ j ≤ n} and edges u 0,t 1 u 1,t 1 ; u 0,t 2 u 1,t 2 ; . . . ; u 0,t k u 1,t k , where 0 ≤ t 1 < t 2 < · · · < t k ≤ n. So the graph consists of an (n + 1) × 3 array of vertices and some flat edges between column 0 and column 1. Extend each edge u 0,ta u 1,ta to a path from u 0,ta to u 2,ta by adding the vertical path from u 1,ta down to u 1,1+t a−1 followed by the edge u 1,1+t a−1 u 2,1+t a−1 and then back up column 2 to u 2,ta . We then obtain paths from u 0,ta to u 2,ta that use all the vertices of columns 1 and 2. This operation is called the vertical downward fill for columns 1 and 2. The vertical upward fill is defined in an obvious analogous manner. These operations are most clearly seen by looking at Figure 3 which shows an example of both vertical fills and makes everything obvious.  Proof. Claim: If HTG(m, n, ), m ≥ 2, is hamiltonian, then the graph HTG(m + 2, n, ) also is hamiltonian. It is easy to see that there must be at least one flat edge between column 0 and column 1 in any Hamilton cycle. So let u 0,j 1 u 1,j 1 , u 0,j 2 u 1,j 2 , . . . , u 0,jt u 1,jt , 0 < j 1 < j 2 < · · · < j t < n, be the flat edges between column 0 and column 1 in some Hamilton cycle.
Subdivide each flat edge with two new vertices in each edge. Remove the central edge in each of the subdivided edges and use vertical fills between the two new columns to obtain a Hamilton cycle in HTG(m + 2, n, ).
Thus, it suffices to prove that HTG(2, n, ) and HTG(3, n, ) are hamiltonian. Consider m = 2 first. For each even i, let P i be the 4-path Start a path with P 0 followed by P followed by P 2 and so on. This eventually closes off to form a cycle. If the cycle is a Hamilton cycle, we are done. If it is not a Hamilton cycle, then perform vertical fills upwards on each flat edge (removing the flat edge) to obtain a Hamilton cycle. Now consider HTG(1, n, ). The column itself is a Hamilton cycle that uses none of the jump edges. By Smith's Theorem [18] there is a second Hamilton cycle C and it must use some jump edges. Each jump edge has the form u 0,i u 0,j with i odd and j = i+ even. Let 0 < i 1 < i 2 < · · · < i t < n be the odd subscripted vertices of the jump edges in C. Add two columns whose vertices are labelled conventionally. Replace the jump edge u 0,ir u 0,ir+ with the jump edge u 2,ir u 0,ir+ and add the flat edge u 0,ir u 1,ir for each i 1 , i 2 , . . . , i t . Now use vertical fills between columns 1 and 2 to obtain a Hamilton cycle in HTG(3, n, ) completing the proof.
The second question is not yet settled and we state it as a research problem.
Research Problem 1. Is every HTG(m, n, ) Hamilton-laceable? Some comments about the preceding problem are in order. It is a signifcant problem because an affirmative answer implies that the family of connected Cayley graphs of valency at least 3 on generalized dihedral groups satisfies the conclusions of the Chen -Quimpo Theorem. A special conclusion from this, of course, is that every connected Cayley graph on a dihedral group is hamiltonian. The fact that the latter conclusion still is unsettled is a frustrating situation.
There has been some progress on Research Problem 1. In [2] it is proved that HTG(m, n, ) is Hamilton-laceable whenever m is even. This leaves the case that m is odd. A few special cases for m = 1 are solved in [3]. The following result is due to McGuinness [13]. His manuscipt contains a long proof and was not published. Consequently, we provide a short proof here for convenience.

Cycle Structure
We now look at cycles in honeycomb toroidal graphs with respect to two properties: girth and cycle spectrum. Throughout this section we use the important convention that the notation HTG(m, n, ) always is in normal form, that is, ≤ n/2. This convention is possible because HTG(m, n, ) is isomorphic to HTG(m, n, n − ). Hence, the information given with respect to assumes n ≥ 2 .
There are no odd length cycles because honeycomb toroidal graphs are bipartite. All HTG(m, n, ) contain 6-cycles (K 4 is not a honeycomb toroidal graph) implying that the girth is either 4 or 6. The next result handles the girth situation and is given without its easy proof.
We now consider the cycle spectrum property. Recall that a graph is even pancyclic if it contains all possible even length cycles from length 4 through 2 n/2 , where n is the order of the graph. Given that connected bipartite Cayley graphs of valency at least 3 on abelian groups are even pancyclic [1] and honeycomb toroidal graphs are Cayley graphs on groups that are close to being abelian, we expect that the latter graphs should have a rich cycle spectrum.
Cycles whose lengths are congruent to 2 modulo 4 are straightforward as the following easily proved result indicates.

Theorem.
The graph HTG(m, n, ) has cycles of length L for all L satisfying L ≡ 2(mod 4) and 6 ≤ L ≤ mn.
From Theorems 5.1 and 5.2, we see that cycles whose lengths are multiples of 4 are of interest. Honeycomb toroidal graphs HTG(m, n, ) for m ≥ 3 and n > 4 have a simple 12-cycle lying in three columns so that lengths 4 and 8 become the only possible missing values once it is seen how to increase cycle lengths by 4 at a time. The cycle spectrum problem was settled for HTG(m, n, ), when m ≥ 3, in [15]. We summarize their results in Table 1. Any of the graphs not listed in the table are even pancyclic. The missing even cycle lengths from 4 through mn − 2 are displayed in the right column.
This leaves the spectrum problem unsettled for m = 1 and m = 2. The honeycomb toroidal graphs for m = 1 were seen to be crucial for the Hamilton laceability question so that they are an interesting subclass. As a side note, HTG(1, 14, 5) is the Heawood graph so that the subclass contains well-known graphs.  Table 1 When m = 1 it is easy to check that HTG(1, n, 3) is even pancyclic. For = 5, HTG(1, n, 5) is missing only a 4-cycle for even n ≥ 14. For = 7, HTG(1, n, 7) is missing only a 4-cycle for even n ≥ 18.
Using methods from [15], it is not hard to show that there are cycles of all lengths that are multiples of 4 lying between 12 and n inclusive. This means the only possible missing cycle lengths are 4 and 8.
Theorem 5.1 provides the information on 4-cycles and it is easy to see they all are even pancyclic. So 8-cycles turn out to be of the most interest. The calculations used to determine the HTG(1, n, ) which contain an 8cycle are tedious and we give two examples to show how it is done. It is based on looking at the subpaths of the cycle C = u 0 , u 1 , u 2 , . . . , u n−1 , u 0 . We also may assume that the edge u 1 , u 1+ belongs to any 8-cycle because of rotational automorphisms of the graph.
If an 8-cycle has just a single subpath of C, then = 7 must hold and we are working with > 7 so that there must be at least two subpaths. If there are two subpaths, one possibility is that one path has length 1 and the other has length 5. There are several subcases one of which is This implies that = (n + 3)/3.
It is trivial to find an 8-cycle when n = 6 or n = 8, so that we need consider only values of n ≥ 10. An 8-cycle must intersect each of the two column cycles in the same number of subpaths. By considering the possible intersections, 8-cycles occur as shown in Table 2. This table differs from Table 1 in that any honeycomb toroidal graph not mentioned in the table for m = 1 or m = 2 is missing both 4-cycles and 8-cycles and no others of even length in the feasible range.

Paths And Diameter
The diameter of a connected graph is the maximum distance between pairs of distinct vertices in the graph. This parameter is of interest to anyone concerned with the propagation of information throughout a network. As this involves distances between vertices, we are interested in shortest paths in honeycomb toroidal graphs. The next two lemmas provide useful information about shortest paths in honeycomb toroidal graphs. Some terminology is necessary before stating them.

The graphs
Missing cycle lengths L HTG (1, n, 3), n ≥ 6 none HTG(1, n, n/2), n ≡ 2(mod 4) none HTG(1, n, (n − 2)/2), n ≡ 0(mod 4) none HTG (2, Table 2 When talking about directions in which edges are traversed, travelling along a flat edge from column i to column i+1 is one direction and travelling from column i + 1 to column i is the other direction. Similarly, the two directions for jump edges are from column 0 to column m − 1 and vice versa. 6.1 Lemma. Every jump edge in a shortest path in HTG(m, n, ) is traversed in the same direction.
Proof. If a shortest path contains no jump edge, there is nothing to prove so let P be a shortest path in HTG(m, n, ) containing a jump edge. Suppose the first jump edge encountered when traversing P is u 0,j u m−1,j− , that is, we traverse it from column 0 to column m − 1. Suppose the next jump edge encountered along P has the form u m−1,k u 0,k+ , that is, it is traversed from column m − 1 to column 0.
This implies that the subpath P of P from u m−1,j− to u m−1,k has no jump edges and the second subscript has changed from j − to k. This is done only by vertical edges in various columns. The change from j to k + is the same as the change from j − to k. Hence, we may delete the subpath from u 0,j to u 0,k+ and replace it with the vertical changes in P translated by projected onto column 0 . This gives us a shorter walk (some edges may be duplicated via the projection) from u 0,0 to the terminal vertex of P . This is a contradiction to P being a shortest path.
A similar contradiction arises if the traversals of two consecutive jump edges are reversed. Therefore, all the jump edges in a shortest path go from column 0 to column m − 1 or vice versa.
6.2 Lemma. Let a shortest path P in HTG(m, n, ) have jump edges. if there are flat edges between the same two columns in P , they must be separated by a jump edge. In particular, if P has no jump edges, then there is at most one flat edge between two columns in P .
Proof. Let u i,j u i+1,j and u i,k u i+1,k be succesive appearances of flat edges between columns i and i + 1, 0 ≤ i < m − 1. Suppose that the first edge is traversed from u i,j to u i+1,j . If there is no jump edge between u i,j u i+1,j and the edge u i,k u i+1,k , then there are vertical edges taking the second subscript from j to k no matter which direction u i,k u i+1,k is traversed.
In either case, remove the subpath of P from u i,j to u i,k and replace it with the projection of the vertical edges onto column i. This yields a shorter walk with the same terminal vertices which is a contradiction. Similar arguments work if the edge u i,j u i+1,j is traversed in the opposite direction. The conclusion follows from this.
Consider the special graph HTG(m, n, 0). If we are looking for a shortest path from u 0,0 to u i,j , it is clear that we need vertical edges taking us to row j and flat edges (the jump edge is also flat in this case) taking us to column i. So if i ≤ m/2, we use flat edges in the direction left to right, and if i > m/2, we take a jump edge from column 0 to column m − 1 followed by flat edges from right to left. We use vertical edges as required to reach row j. It is straightforward to obtain the diameter as shown in Table 3.
The preceding worked easily because the jump edges change the second subscript by zero. Other values for the jump edges allow for big changes in shortest paths because a large jump edge value allows large changes in the second subscript. For example, suppose we are trying to increase the second subscript as much as possible. We can start a path at u 0,0 and reach the vertex u m−1,m−1 when we first reach column m − 1. We follow this with the edge u m−1,m−1 u m−1,m and then the jump edge u m−1,m u 0,m+ .
We now have a path from u 0,0 to u 0,m+ of length 2m. If instead we took the path from u 0,0 to u 0,m+ up column 0, it has length m + . Thus, if > m, we have a shorter path by using a jump edge. Lemma 6.1 provides some help because it tells us that if we use more than one jump edge in a shortest path, we must use them in the same direction which forces many edges to be used between their appearances.
Research Problem 2. Determine the shortest paths between vertices in an arbitrary HTG(m, n, ).
The diameters of a few honeycomb toroidal graphs have been determined in [17,19,21] and we summarize their results in the following table. Note that [19] corrects an error for the diameter of HTG(m, 2m, m) given in [17].
The preceding problem undoubtedly has many subcases as the value of the jump varies. Lemmas 6.1 and 6.2 allow us to determine that the diameter of HTG(1, n, ) is 2 n/ + 1 whenever ≤ √ n. We shall not present the tedious proof of this fact, but mention it just to indicate the kinds of complications that likely arise in considering the preceding problem.

Automorphisms
Honeycomb toroidal graphs are Cayley graphs [4] on a generalized dihedral group. This means they are vertex-transitive. As mentioned earlier, HTG(1, 14, 5) is the Heawood graph and its automorphism group has order 336 in spite of the graph having only 14 vertices. On the other hand, the automorphism group of HTG(1, 14, 3) has order only 28. So we see there may be wide variations in the automorphism groups of these graphs. This suggests the next problem.
Research Problem 4. Determine the automorphism group of an arbitrary HTG(m, n, ) in terms of the parameters m, n and .
Given a family of Cayley graphs, there is interest in determining those with minimal automorphism groups. In this case that means those that are GRRs, that is, those for which |Aut(HTG(m, n, )| = mn.
Little is known about the preceding question. One result in this direction comes from [10] in which the following result is proved.

Conclusion
The family of graphs under discussion are of interest for several reasons and we have looked at them primarily from a graph theoretic viewpoint. There has been considerable work done on algorithmic aspects of honeycomb toroidal graphs. Most of the concern is with routing, broadcasting, bisection width, semigroup computation and cost. Again, most of the work has dealt with the special honeycomb toroidal graphs introduced in [17] and their extensions. So there is room for research for the entire family of honeycomb toroidal graphs. There is background for the algorithmic work in [6,8,11,14,16,17].
We also have presented some specific research problems that we find interesting. This is a family of graphs worthy of much further investigation.