¿^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 18 (2020) 223-239
https://doi.org/10.26493/1855-3974.1931.9cf
(Also available at http://amc-journal.eu)
Generation of local symmetry-preserving operations on polyhedra
Pieter Goetschalckx * ©, Kris Coolsaet ©, Nico Van Cleemput ©
Ghent University, Krijgslaan 281-S9, 9000 Ghent, Belgium
Received 8 February 2019, accepted 4 April 2020, published online 19 October 2020 Abstract
We introduce a new practical and more general definition of local symmetry-preserving operations on polyhedra. These can be applied to arbitrary embedded graphs and result in embedded graphs with the same or higher symmetry. With some additional properties we can restrict the connectivity, e.g. when we only want to consider polyhedra. Using some base structures and a list of 10 extensions, we can generate all possible local symmetry-preserving operations isomorph-free.
Keywords: Graph theory, polyhedra, symmetry, chamber systems. Math. Subj. Class. (2020): 05C10, 68R10
1 Introduction
Symmetry-preserving operations on polyhedra have a long history - from Plato and Archimedes to Kepler [11], Goldberg [9], Caspar and Klug [4], Coxeter [6], Conway [5], and many others. Notwithstanding their utility, until recently we had no unified way of defining or describing these operations without resorting to ad-hoc descriptions and drawings. In [2] the concept of local symmetry-preserving operations on polyhedra (lsp operations for short) was introduced. These are operations that are locally defined - on the chamber level, as explained in the next section - and therefore preserve the symmetries of the polyhedron to which they are applied. This established a general framework in which the class of all lsp operations can be studied, without having to consider individual operations separately. It was shown that many of the most frequently used operations on polyhedra (e.g. dual, ambo, truncate, . . . ) fit into this framework.
But of course we sometimes do want to examine the operations individually, e.g. to check conjectures on as many examples as possible before we try to prove them, or to
* Corresponding author.
E-mail addresses: pieter.goetschalckx@ugent.be (Pieter Goetschalckx), kris.coolsaet@ugent.be (Kris Coolsaet), nico.vancleemput@gmail.com (Nico Van Cleemput)
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
224
Ars Math. Contemp. 18 (2020) 187-210
find operations with certain properties. We can do this for a few operations by hand, but a computer can do this a lot faster, and in a systematic way such that no operations are missed.
In this paper we shall slightly extend the definition of lsp operation so it can be applied to any graph embedded on a compact closed surface1, and at the same time provide a reformulation of these operations as decorations, which will turn out to be easier to use in practice.
2 Decorations and lsp operations
Every embedded graph G has an associated chamber system CG [7]. This chamber system is obtained by constructing a barycentric subdivision of G by adding one vertex in the center of each edge and face of G, and edges from each center of a face to its vertices and centers of edges. These vertices can be chosen invariant under the symmetries of G. In CG, each vertex has a type that is 0, 1, or 2, indicating the dimension of its corresponding structure in G. Each edge has the type of the opposite vertex in the adjacent triangles. In Figure 1, the chamber system of the plane graph of a cube is given. The original graph consists of the edges of type 2 in the chamber system.
Figure 1: The barycentric subdivision of the plane graph of a cube. Edges of type 0 are red, edges of type 1 are green and edges of type 2 are black.
We use the drawing conventions from Figure 1 for the types of the edges in all figures. Since the vertex types can be deduced from the edge types, we do not display them in the figures.
Definition 2.1. A decoration D is a 2-connected plane graph with vertex set V and edge set E, together with a labeling function t: V U E ^ {0,1, 2}, and an outer face which contains vertices v0, vi, v2, such that
1.	all inner faces are triangles;
2.	for each edge e = (v,w), {t(e),t(v),t(w)} = {0,1, 2};
1 All graphs in this paper are embedded graphs, and a subgraph has the induced embedding.
P. Goetschalckx et al.: Generation of local symmetry-preserving operations on polyhedra 225
3.	for each vertex v with t(v) = i, the types of incident edges are j and k with {i,j,k} = {0,1, 2}. Two consecutive edges with an inner face in between can not have the same type;
4.	for each inner vertex v
t(v) = 1 ^ deg(v) = 4 t(v) = 1 ^ deg(v) > 4
for each vertex v in the outer face and different from v0, v^ v2
t(v) = 1 ^ deg(v) = 3 t(v) = 1 ^ deg(v) > 3
and
t(vo),t(v2) = 1
t(vi) = 1 ^ deg(vi) = 2
t(vi) = 1 ^ deg(vi) > 2.
Note that condition 3 implies that all inner vertices have an even degree.
For all {i, j, k} = {0,1,2}, the k-side of a decoration D is the path on the border of the outer face between v4 and v that does not pass through vk.
We can fill each triangular face of a chamber system CG with a decoration, by identifying the vertex of type i with v4 for i G {0,1, 2} and identifying corresponding vertices on the boundary. This results in a new chamber system CG> of a new graph G", as can be seen in Figure 2.
the one in black.
This is very similar to the lsp operations of [2]. We are constructing graphs by subdividing the chambers of the chamber system. One key difference is that we impose no
226
Ars Math. Contemp. 18 (2020) 187-210
restrictions on the connectivity. This means that we can apply decorations to arbitrary embedded graphs, but when applied to a polyhedron - i.e. a 3-connected plane graph - it is possible that the result has a lower connectivity. We will address this problem later with additional restrictions on decorations.
For now, we will repeat Definition 5.1 of [2] without the restrictions on the connectivity.
Definition 2.2. Let T be a connected periodic tiling of the Euclidean plane with chamber system CT, that is given by a barycentric subdivision that is invariant under the symmetries of T. Let v0, v\,v2 be points in the Euclidean plane so that for 0 < i < j < 2 the line Li,j through vi and vj is a mirror axis of the tiling.
If the angle between L0,i and L2,i is 90 degrees, the angle between L2,i and L2,0 is 30 degrees and consequently the angle between L01 and L0 2 is 60 degrees, then the triangle v0, v1, v2 subdivided into chambers as given by CT and the corners v0, v1, v2 labelled with their names v0, v1, v2 is called a local symmetry-preserving operation, lsp operation for short.
The result O(G) of applying an lsp operation O to a connected graph G is given by subdividing each chamber C of the chamber system CG with O by identifying for 0 < i < 2 the vertices of O labelled vi with the vertices labelled i in C.
An lsp operation is called k-connected for k G {1,2,3} if it is derived from a k-con-nected tiling T. So the original definition was for 3-connected lsp operations only. In order to correctly determine the connectivity, we first need to identify which chamber systems correspond to k-connected graphs. To decide whether a graph G is k-connected based on its chamber system CG, we can look at the type-1 cycles in CG. A type-1 cycle is a cycle in the subgraph of CG that consists of the type-1 edges only. A type-1 cycle is empty if there are no vertices on the inside or on the outside of the cycle in this type-1 subgraph. Note that in the graph CG these cycles are not necessarily empty.
Lemma 2.3. A plane graph G is
1.	2-connected if and only if CG contains no type-1 cycles of length 2;
2.	3-connected if and only if G is 2-connected and CG contains no non-empty type-1 cycles of length 4.
Proof.
1.	Suppose CG contains a type-1 cycle of length 2. This cycle contains one type-0 vertex v, incident to at least one type-2 edge inside the cycle and at least one type-2 edge outside the cycle (see Figure 3a), because CG is a barycentric subdivision. It is clear that v has to be a cut-vertex of G.
Conversely, if G has a cut-vertex v, there is a face of G for which v occurs at least two times in its border. In CG this face corresponds with a type-2 vertex, incident with at least two type-1 edges to v. These edges form a type-1 cycle in CG.
2.	Suppose CG contains a non-empty type-1 cycle of length 4, as can be seen in Figure 3b. This cycle contains two type-0 vertices v and w, with incident type-2 edges at both sides of the cycle. Removing v and w from G results in a disconnected graph.
If G is 2-connected but not 3-connected, there are two vertices v and w that disconnect G when removed. So there are two non-empty subgraphs of G that are only
P. Goetschalckx et al.: Generation of local symmetry-preserving operations on polyhedra 227
connected by v and w, as in Figure 3b. This means that there is a non-empty type-1 cycle in CG.	□
o
(a) not 2-connected
(b) 2-connected but not 3-connected
Figure 3: Two graphs with type-1 cycles. The gray area contains the graph. Only the type-1 edges of the chamber system are shown. The type-0 vertices are red and the type-2 vertices are black.
Note that this theorem only holds for plane graphs, since the proof relies on the Jordan curve theorem. A counterexample to an equivalent theorem for embedded graphs of higher genus is the dual of a 3-connected graph on the torus, which can have a 2-cut (see [1]).
Since we introduced a more general definition of lsp operations, we can also formulate a more general version of Theorem 5.2 in [2].
Theorem 2.4. If G is a k-connectedplane graph with k G {1, 2, 3}, and O is a k-connected lsp operation, then O(G) is a k-connected plane graph.
Proof. It is clear that O(G) is a plane graph. For k = 1, we know that T and G are connected, and it follows easily that O(G) is connected. For k = 3, the proof is given in [2]. For k = 2, we will prove that there is no cut-vertex in O(G).
A type-1 cycle of length 2 in CO(G) is either completely contained in one chamber of CG2, or it is split between two chambers of CG (see Figure 4). Both cases cannot appear, as for any chamber (resp. any pair of adjacent chambers) there is an isomorphism between this chamber (resp. these two chambers) and the corresponding area in T, and according to Lemma 2.3 T has no type-1 cycles of length 2.
This implies that CO(G) contains no type-1 cycles of length 2, and thus, invoking once again Lemma 2.3, O(G) contains no cut-vertices.	□
2With a chamber of Cq in C'o(q), we mean the area that was a chamber of Cq before it was subdivided by O.
228
Ars Math. Contemp. 18 (2020) 187-210
We can prove similar properties for decorations, but it is easier to use the correspondence between lsp operations and decorations. Although the way they are defined is rather different, in reality they are the same thing. The triangle v0, v1,v2 of an lsp operation that is derived from a tiling has exactly the properties of a decoration, and each decoration can be derived as an lsp operation from a tiling.
Theorem 2.5. Each decoration defines an lsp operation and vice versa.
Proof. It is straightforward that the graph defined by an lsp operation is unique and satisfies the conditions of Definition 2.1. We still have to prove that each decoration defines an lsp operation.
Given a decoration D, we can take the hexagonal lattice H and use D to decorate each chamber of the chamber system CH. The result will be a chamber system CT of a tiling T.
We will first prove that the type-2 subgraph of D is connected, by induction on the number of triangles. There is always at least one triangle in D that shares one or two edges with the outer face. We remove these edges, and call the result D'. It is clear that D' still satisfies properties 1-3 of Definition 2.1, and by induction its type-2 subgraph is connected. If one of the removed edges has type 2, it is connected to D' by a vertex of type 0 or 1 with degree at least 3, and therefore it is connected to the type-2 subgraph of D'.
Given vertices u and v in the type-2 subgraph of CT, there exists a sequence of chambers C0,... ,Cn of H such that two consecutive chambers Cj and Ci+1 share one side, and u is contained in C0 and v in Cn. Since there are at least two vertices on each side of D, and they are not both of type 2, at least one of them is in the type-2 subgraph of CT. Thus, there is a type-2 path between u and v that passes through all chambers in the sequence C0,... ,Cn, and the type-2 subgraph of CT is connected. It follows immediately that T is connected too.
We can choose the vertices of one chamber of CH in T as v0, v1 and v2. This satisfies the properties of Definition 2.2, and it is clear that the decoration defined by the triangle
v0,v1,v2 is equal to D.	□
This correspondence can be further extended to 2-connected and 3-connected operations.
Definition 2.6. A 2-connected decoration is a decoration with
1.	no type-1 cycles of length 2;
2.	no internal type-1 edges between two vertices on a single side. Definition 2.7. A 3-connected decoration is a 2-connected decoration with
1.	no type-1 edge between sides 0 and 2;
2.	no non-empty type-1 cycles of length 4.
Note that, when seen as a graph, a decoration is always at least 2-connected.
Theorem 2.8. Each 2-connected decoration D defines a 2-connected lsp operation and vice versa.
P. Goetschalckx et al.: Generation of local symmetry-preserving operations on polyhedra 229
Proof. A 2-connected decoration is a decoration, so it follows from Theorem 2.5 that D defines an lsp operation. We still have to prove that the corresponding tiling T is 2-con-nected. If T is not 2-connected, there is a type-1 cycle of length 2 in CT. If this cycle is completely contained in the triangle v0, v\, v2, there is a cycle of length 2 in D too, which is impossible. The only other possibility is that the cycle of length 2 is cut in half by Lj, but then there would be an internal type-1 edge between 2 vertices on Lj, which is a side of D.
A 2-connected lsp operation with corresponding tiling T defines a decoration D according to Theorem 2.5. We still have to prove that the extra conditions of Definition 2.6 are satisfied. If there is a type-1 cycle of length 2 in D, this cycle occurs in CT too, and T would not be 2-connected. If there is an internal type-1 edge between 2 vertices on the same side, this will result in a cycle of length 2 in T because this side lies on a mirror axis of T.	□
Theorem 2.9. Each 3-connected decoration D defines a 3-connected lsp operation and vice versa.
Proof. A 3-connected decoration defines a 2-connected lsp operation. If T is not 3-con-nected, there is a non-empty type-1 cycle of length 4. If this cycle is completely contained in the triangle v0, vi, v2, there is a type-1 cycle of length 4 in D. If the cycle is cut in half by Lj, there is an internal type-1 path of length 2 between 2 vertices on Lj, which is a side of D. If the cycle is cut in four, as in Figure 5, there is a type-1 edge between sides 0 and 2.
A 3-connected lsp operation with corresponding tiling T defines a 2-connected decoration D. If there is a type-1 cycle of length 4 in D, this cycle occurs in CT too, and T would not be 3-connected. If there is an internal type-1 path of length 2 between 2 vertices on the same side, or a type-1 edge between sides 0 and 2, this will result in a cycle of length 4 in T.	□
3 Predecorations
The generation of all decorations will be split into two phases. In the first phase, we will construct the type-1 subgraph, consisting of all edges of type 1.
Let nA be the number of vertices in the type-1 subgraph of degree 1 with a neighbouring vertex of degree 2, nB the number of remaining vertices of degree 1, and nC the number of quadrangles with three vertices of degree 2.
230
Ars Math. Contemp. 18 (2020) 187-210
K>
(a)nA	(b) n-B	(c)nc
Figure 6: The subgraphs counted as ha, »/ ; and nC-
Lemma 3.1. Let D be a decoration. The type-l subgraph Di of D has the following properties:
1.	all inner faces are quadrangles;
2.	each inner vertex has degree at least 3;
3.	iiA < 2 and ua + kb + nc < 3.
Proof. It follows immediately from the properties of a decoration (Definition 2.1) that the inner faces of D\ are quadrangles and the inner vertices have degree at least 3.
Each area bounded by a quadrangle in contains one vertex of type 1 in D. The only other difference between D and l)\ is in the outer face of l)\, where type-l vertices of degree 3 in D (a 3-completion), and at most one of degree 2 in I) (a 2-completion), can be present in D. If there is a type-l vertex of degree 2, then that vertex is i'i. An example can be seen in Figure 7.
The subgraph in Figure 6c can only occur if the rightmost vertex v of degree two is v0, i'i or i>2, or if r is a type-l vertex of degree 2 connected to this vertex. Each of the three vertices of degree 2 in this subgraph of I) corresponds to v0, n, ''■_< or a vertex of degree at least 4 in D. The inner edges of the quadrangle in D contribute exactly one to the degree of these vertices. This implies that either there is a 2-completion here (in which case i'i is connected to v), or there are two 3-completions which do not involve v (in which case v is v0, Hi or v2).
The subgraph in Figure 6b can only occur if the rightmost vertex v is v0, n or This vertex of degree 1 in l)\ corresponds to a vertex of degree at most 3 in I), which is only possible in v0, i>i or n2-
The subgraph in Figure 6a can only occur if the rightmost vertex v is v0 or . There are two neighbouring cut-vertices of in this subgraph, which do not correspond to cut-vertices in D. This is only possible if both of these vertices are the middle vertex of a 3-completion. This increases the degree of v in I) to 2, which is only possible in v0 or i>2. The degree of v can be 3 if there is a 2-completion too, but then r is contained in this 2-completion and v still has to be v0 or
We find that nA < Ifi'o, i'2}I = 2 and nA + nB + nc < Ifi'o, fi, ^2}! = 3.	□
Definition 3.2. A predecoration is a connected plane graph with an outer face that satisfies the properties of Lemma 3.1.
Given a predecoration P, we can try to add edges, vertices and labels to get a decoration with P as its type-l subgraph. We will have to add one type-l vertex in each inner face of P, as in Figure 7. Then we can add type-l vertices in the outer face, and connect them to three consecutive vertices of P. Finally, we can add a type-l vertex in the outer face and connect it to two consecutive vertices of P. This vertex has to be i'i.
P. Goetschalckx et al.: Generation of local symmetry-preserving operations on polyhedra 231
Figure 7: A predecoration with a possible completion. The edges of type 0 and 2 are both shown in black.
By definition, the type-1 subgraph of a decoration D is a predecoration. Unfortunately, not each predecoration corresponds to a type-1 subgraph of some decoration. This is e.g. the case if there are too many cut-vertices, as in Figure 8.
4 Construction of predecorations
All predecorations can be constructed from the base decorations K2 and C4 (see Figure 9) using the 10 extension operations shown in Figure 10. We will prove this by showing that each predecoration, with the exception of K2 and C4, can be reduced by the inverse of one of the extension operations. We will then use the canonical construction path method [12] to generate all predecorations without isomorphic copies.
Given a predecoration P, we will choose a canonical parent of P. This is a predecoration obtained by applying one of the reductions to P. We will always use the reduction with the smallest number among all possible reductions. It is possible that there is more than one way to apply this reduction to P, and if P has non-trivial symmetry, some of these can result in the same parent. If we choose one special edge in the subgraph that is affected by the reduction operation, each way to apply this reduction corresponds to an edge of P. We can choose an orbit of edges under the symmetry group of P by constructing a canonical labeling of the vertices - similar to [3] - and choosing the orbit of the edge with the lowest numbered vertices. The canonical parent of P is then obtained by applying the corresponding reduction.
During the construction, we will try each possible extension in all possible ways, and then check if it is the inverse of the reduction used to get the canonical parent of the result-
•-• • »
Figure 8: A predecoration that cannot be completed.
•-• *——
Figure 9: The base predecorations.
232
Ars Math. Contemp. 18 (2020) 187-210
1.
3.
4.

ILU
2.
5.

6- ►>
9.
10.
□ □
7.

Figure 10: The extensions. In the first row, the subgraphs before the extension is applied are given. New edges and vertices are green, and vertices that are broken apart in two new vertices are red. The outer face is always on the outside, and shadowed parts contain at least one vertex.
ing predecoration. If that is the case, we can continue to extend this predecoration.
It is possible to construct all predecorations with fewer extensions, but it is important that a canonical reduction always results in a valid predecoration. The order of extensions ensures that a canonical reduction never increases nA, and extensions 5-7 ensure that a canonical reduction never increases ua + » /; + »< •• Extensions 8-10 are necessary when none of the other reductions are possible, so that each predecoration different from the base decorations has a possible reduction. We will prove this in Lemma 4.2 and Theorem 4.3.
Lemma 4.1. An extension applied to a predecoration results in another predecoration if it keeps na < 2 and iia + + nc < 3. Only extensions 1, 2 and 5 possibly violate this condition.
Proof. It is easy to see that each extension can only create new inner faces that are quadrangles, and inner vertices with degree at least 3.
The only extensions that can increase ua are extensions 1 and 2. The only extension
that can increase nB is extension 2. The only extension that can increase nc is extension 5.
□
This makes it easier to keep count of nA, nB and nc during the construction.
Lemma 4.2. Let P be a predecoration different from the base predecorations. By applying one of the reductions from Figure 10, P can be reduced to a graph containing fewer vertices or a graph containing the same number of vertices but fewer edges.
P. Goetschalckx et al.: Generation of local symmetry-preserving operations on polyhedra 233
Furthermore, if we apply the reduction with the smallest number among all possible reductions, the resulting graph is again a predecoration.
Proof. For the first part, it is clear that each reduction results in a 'smaller' graph, so we only need to verify that at least one reduction can be applied. If P contains at least one quadrangle, there is at least one quadrangle Q with an edge in the outer face. Since P is not C4, there is at least one other vertex not contained in Q in the graph, and reduction 10 is possible. If there is no quadrangle in P, reduction 1 is possible.
For the second part, it is immediately clear that all reductions preserve the properties that all inner faces are quadrangles and that all inner vertices have degree at least 3. It remains to be proven that for the new graph nA < 2 and nA + nB + nC < 3.
Some reductions can increase nA, nB or nC, but only if another reduction with a smaller number can also be applied. This is the reason that we need so many extension operations in that particular order. In Table 1, all these situations are given.
Table 1: Table with possible reductions. Read this table as:
Reduction i can increase nX, but only if nY is decreased by the same amount.
Reduction i can increase nX, but only if reduction j/k can be applied too.
reduction	nA	nB	nC
1		nA	
2	1	1	nB
3,4	1		
5, 6,7	1	1	3/4
8	2/5	5	6/7
9	2/8	8	8
10	2/9	9	9
It is impossible to increase nA with a reduction that has the smallest possible number. Therefore, we still have nA < 2 in the new graph.
Reduction 1 can increase nB, but only by removing a vertex of degree 2 neighbouring a vertex of degree 1, i.e. by decreasing nA by the same amount. Therefore, we still have nA + nB + nC < 3 in the new graph.
Reduction 2 can increase nC, but only by decreasing nB by the same amount. Therefore, we still have nA + nB + nC < 3 in the new graph.	□
Theorem 4.3. The algorithm described in Algorithm 1 generates all predecorations. Proof. This follows immediately from [12] and Lemma 4.2.	□
5 Construction of decorations
Now that we can construct all predecorations, we can use the homomorphism principle [10] and complete each predecoration in all possible ways to get all k-decorations with Algorithm 2. We first have to compute the symmetry group of the predecoration, in order to avoid completions that result in the same decoration. After the first 4 steps, all symmetry is broken by choosing v0, vi and v2.
234
Ars Math. Contemp. 18 (2020) 187-210
Algorithm 1 Construction of predecorations function Extend(P) output P
for i = 1,..., 10 do
for O an orbit of edges in the outer face of P do e ^ edge in O
P' ^ apply extension i to edge e of P if P canonical parent of P' then
Extend(P ')
for G a base predecoration do
Extend(P )
Algorithm 2 Complete a predecoration in all possible ways
1.	If nA > 0, label the corresponding vertices of degree 1 with v0 or v2 in all non-isomorphic ways.
2.	If nB + nC > 0, label the corresponding vertices with v0, vi or v2 in all non-isomorphic ways.
3.	If v1 is not yet chosen, label an outer vertex with v1 or add a new type-1 vertex v1 of degree 2 in the outer face in all non-isomorphic ways.
4.	If v0 or v2 is not yet chosen, label two outer vertices with v0 and v2 in all non-isomorphic ways.
5.	Fill all inner quadrangles with a type-1 vertex.
6.	Add type-1 vertices of degree 3 in the outer face in all possible ways, such that there are no cut-vertices or vertices of degree 2 left.
7.	Check whether the result is a k-decoration.
P. Goetschalckx et al.: Generation of local symmetry-preserving operations on polyhedra 235
We do not have to take isomorphisms into account, since two isomorphic decorations will have isomorphic predecorations.
Note that it might not be possible to complete a predecoration in Step 6 such that there are no cut-vertices left.
5.1	Connectivity
In Step 7, we will always obtain a decoration. The additional properties for 2-connected decorations and 3-connected decorations have to be checked. The properties in the outer face cannot be checked earlier in the construction process, because they depend on the chosen completion. But we can prevent type-1 cycles of length 2 and cycles of length 4 during the construction. It is clear that once a type-1 cycle is created during the construction, it cannot be destroyed later. So we only have to avoid the creation of the first type-1 cycle of length 2 or 4.
The only way to create a first type-1 cycle of length 2 is by applying extension 10 to a predecoration with an outer face of size 4. This can easily be avoided. The only way to create a non-empty type-1 cycle of length 4 is by applying extension 10 to a predecoration with an outer face of size 6. We can avoid this too.
To check the other properties after the completion, we can loop over the outer face of the decoration, and mark all vertices one inner edge away from side i with i. If we encounter a vertex on side i that is marked with i, the decoration is not 2-connected. If a vertex is marked two times with the same number, or a vertex on side 1 is marked with 0 or vice versa, the decoration is not 3-connected.
5.2	Inflation rate
As mentioned in [2], the impact of an operation on the size of a polyhedron can be measured by the inflation rate. This is the ratio of the number of edges before and after the operation, and is equal to the number of chambers in the decoration.
Although it is interesting to construct all possible decorations, we are more interested in the decorations with a given inflation rate. Unfortunately, we cannot determine the inflation rate before the predecoration is completed as decorations with different inflation rates might have the same predecoration, but we can compute lower and upper bounds.
Given a predecoration P, for each decoration that has P as its underlying predecoration, each quadrangle of P corresponds to 4 chambers and each cut-vertex of which the removal leaves k > 2 components requires 2(k - 1) extra chambers. So
4 • (number of quadrangles) + 2 • ^ (occurences in outer face - 1)
cut-vertices
is a lower bound for the inflation rate. The maximal inflation rate of a predecoration is reached by adding as much type-1 vertices as possible in the outer face. This will result in exactly one chamber for each edge in the outer face. In combination with the 4 chambers in each quadrangle, this results in 2 chambers (one at each side) for each edge of the predecoration. So the maximal inflation rate is
2 • (number of edges).
If the lower bound for the inflation rate of a predecoration is already higher than the desired inflation rate, we do not have to extend it further as it can only increase. If the
236
Ars Math. Contemp. 18 (2020) 187-210
upper bound is lower than the desired inflation rate, we have to extend it, but we do not have to try to complete it.
Table 2: The number of k-connected decorations up to inflation rate 40. The number of predecorations that can be completed to a decoration with given inflation rate are given too. Not all of these predecorations are constructed for 2-connected or 3-connected decorations.
k-connected decorations
inflation rate	k = 1	k = 2	k=3	predecorations
1	2	2	2	1
2	2	2	2	1
3	4	4	4	1
4	6	6	6	2
5	6	6	4	2
6	20	20	20	4
7	28	28	20	7
8	58	58	54	8
9	82	82	64	7
10	170	168	144	19
11	204	200	132	16
12	496	492	404	50
13	650	640	396	42
14	1432	1400	1112	118
15	1824	1786	1100	109
16	4114	3952	2958	298
17	5078	4900	2769	300
18	11874	11150	7972	749
19	14808	14058	7560	782
20	33978	30998	21300	1902
21	41794	38964	20076	2056
22	97096	85976	56296	4893
23	118572	107784	52380	5419
24	277208	237482	148956	12615
25	337216	298546	138384	14153
26	788342	652236	392096	32665
27	953060	820960	362499	36953
28	2239396	1786222	1027488	84853
29	2697088	2250816	945612	96491
30	6350014	4875076	2687408	220646
31	7618068	6153604	2466156	251104
32	17972390	13262574	7007118	573547
33	21487746	16773086	6409664	654663
34	50805716	35985748	18222032	1491540
35	60573248	45592594	16623268	1706755
36	143425040	97394726	47287986	3878836
37	170530518	123628298	43038260	4446426
38	404413576	262983002	122451618	10085305
39	479711448	334473144	111200316	11582891
40	1139138344	708583784	316474370	26222191
P. Goetschalckx et al.: Generation of local symmetry-preserving operations on polyhedra 237
Table 3: All decorations with inflation rate r up to 8. The green lines are edges of type 1. The black lines are edges of type 0 and 2. For each of the given decorations, the edges of type 0 and 2 can be chosen in two different ways. All decorations except the symmetric ones (marked with a star) can be mirrored. So each starred decoration represents two related lsp operations, and the unstarred ones represent four related lsp operations.
r k=2	k=3
238
Ars Math. Contemp. 18 (2020) 187-210
6 Results
Using Algortihms 1 and 2, we implemented a computer program [8] to generate all k-decorations with a given inflation rate. The results of this program are given in Table 2. The decorations for inflation rates r < 8 are given in Table 3.
The two lsp operations with inflation rate 1 are obviously identity and dual. The lsp operations with inflation rate 2 are ambo and join, and the ones with inflation rate 3 are truncate, zip, needle and kiss. Up to here, all lsp operations were already described by Conway [5] or others. For the left decoration with inflation rate 4, only two of the 4 related lsp operations (chamfer and subdivide) are already named. The first decoration for which none of the related lsp operations (including dual and mirrored ones) are already named, is the 2-connected lsp operation with inflation rate 5. The first unnamed 3-connected lsp operations are the three leftmost decorations with inflation rate 6.
These results are verified for inflation rate up to 23 by an independent implementation that constructs all triangulations, filters the decorations out, applies them to a polyhedron, checks the connectivity and filters the isomorphic ones out.
ORCID iDs
Pieter Goetschalckx © https://orcid.org/0000-0002-3080-3790 Kris Coolsaet © https://orcid.org/0000-0002-7657-900X Nico Van Cleemput © https://orcid.org/0000-0001-9689-9302
References
[1]	D. Bokal, G. Brinkmann and C. T. Zamfirescu, The connectivity of the dual, 2018, arXiv:1812.08510 [math.CO].
[2]	G. Brinkmann, P. Goetschalckx and S. Schein, Comparing the constructions of Goldberg, Fuller, Caspar, Klug and Coxeter, and a general approach to local symmetry-preserving operations, Proc. R. Soc. A 473 (2017), 20170267 (14 pages), doi:10.1098/rspa.2017.0267.
[3]	G. Brinkmann and B. D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem. 58 (2007), 323-357, http://match.pmf.kg.ac.rs/electronic_ versions/Match58/n2/match5 8n2_32 3-357.pdf.
[4]	D. L. D. Caspar and A. Klug, Physical principles in the construction of regular viruses, Cold Spring Harb. Symp. Quant. Biol. 27 (1962), 1-24, doi:10.1101/sqb.1962.027.001.005.
[5]	J. H. Conway, H. Burgiel and C. Goodman-Strauss, The Symmetries of Things, A K Peters, Wellesley, Massachusetts, 2008.
[6]	H. S. M. Coxeter, Virus macromolecules and geodesic domes, in: J. C. Butcher (ed.), A Spectrum of Mathematics, Auckland University Press, Auckland, pp. 98-107, 1971, essays presented to H. G. Forder.
[7]	A. W. M. Dress and D. Huson, On tilings of the plane, Geom. Dedicata 24 (1987), 295-310, doi:10.1007/bf00181602.
[8]	P. Goetschalckx, decogen, 2019, https://github.com/314eter/decogen.
[9]	M. Goldberg, A class of multi-symmetric polyhedra, Tohoku Math. J. 43 (1937), 104-108.
[10] T. Gruner, R. Laue and M. Meringer, Algorithms for group actions applied to graph generation, in: L. Finkelstein and W. M. Kantor (eds.), Groups and Computation II, American Mathematical Society, Providence, Rhode Island, volume 28 of DIMACS Series in Discrete Mathematics
P. Goetschalckx et al.: Generation of local symmetry-preserving operations on polyhedra 239
and Theoretical Computer Science, 1997 pp. 113-122, doi:10.1090/dimacs/028/09, Proceedings of the 2nd DIMACS Workshop held at Rutgers University, New Brunswick, NJ, June 7 -10, 1995.
[11]	J. Kepler, Ioannis Keppleri Harmonices mundi: libri V, Linz, 1619.
[12]	B. D. McKay, Isomorph-free exhaustive generation, J. Algorithms 26 (1998), 306-324, doi: 10.1006/jagm.1997.0898.