Extremal $\varvec{\{ p, q \}}$-Animals

Abstract

An animal is a planar shape formed by attaching congruent regular polygons along their edges. Usually, these polygons are a finite subset of tiles of a regular planar tessellation. These tessellations can be parameterized using the Schläfli symbol $\{p,q\}$, where p denotes the number of sides of the regular polygon forming the tessellation and q is the number of edges or tiles meeting at each vertex. If $(p-2)(q-2)> 4$, $=4$, or $<4$, then the tessellation corresponds to the geometry of the hyperbolic plane, the Euclidean plane, or the sphere, respectively. In 1976, Harary and Harborth studied animals defined on regular tessellations of the Euclidean plane, finding extremal values for their vertices, edges, and tiles, when any one of these parameters is fixed. They named animals attaining these extremal values as extremal animals. Here, we study hyperbolic extremal animals. For each $\{p,q\}$ corresponding to a hyperbolic tessellation, we exhibit a sequence of spiral animals and prove that they attain the minimum numbers of edges and vertices within the class of animals with n tiles. We also give the first results on enumeration of extremal hyperbolic animals by finding special sequences of extremal animals that are unique extremal animals, in the sense that any animal with the same number of tiles which is distinct up to isometries cannot be extremal.

1 Introduction

An animal is a planar shape with a connected interior formed by gluing together a finite number of congruent regular polygons along their edges. Here, we study animals that have extremal combinatorial properties such as having maximally many shared (or interior) edges for a given number of polygons. We refer to animals attaining these optimal values as extremal animals. In the Euclidean plane, extremal animals have been well studied and it is known that they exhibit interesting geometric and combinatorial properties such as being isoperimetric [8], giving contact numbers for optimal disk packing configurations [9], and providing the right shape to produce animals with maximally many holes [14, 20,21,22].

In the hyperbolic plane, combinatorial and geometric properties of extremal animals have not been examined as closely. However, the relevance of extremal animals to other extremal combinatorial problems has already been established. These include optimal disk packing problems [4], the calculation of Cheeger constants [10], the establishment of the exponential growth constant of regular hyperbolic tessellations [15], and the implementation of algorithms to sample certain hyperbolic animals to approximate hyperbolic percolation thresholds [25].

Recently, extremal hyperbolic animals have been used to model and study structures in applied mathematics, such as in crystallography theory for materials with hyperbolic symmetries [3], and in the architecture of circuit quantum electrodynamics [16]. More generally, models based on hyperbolic tessellations have also been used in areas such as Bloch band theory in physics [18], and in quantum error-correcting and quantum storage codes [5, 12], among others. Therefore, having a better understanding of extremal hyperbolic animals might lead to interesting insights, results, techniques, and new research questions in these areas.

The families of animals that we study in this paper are formed by finite subsets of tiles of regular Euclidean and hyperbolic tessellations. These tessellations can be parameterized using the Schläfli symbol $\{p,q\}$, where p denotes the number of sides of the regular polygon forming the tessellation and q is the number of edges or tiles meeting at each vertex. It is well known that if $(p-2)(q-2)> 4$, $=4$, or $<4$, then the tessellation corresponds to the geometry of the hyperbolic plane, the Euclidean plane, or the sphere, respectively. We call an animal living in a $\{p,q\}$-tessellation a $\{p,q\}$-animal. The most well-known families of animals are those living in the Euclidean tessellations, namely for $\{p,q\}$ either $\{3,6\}$, $\{4,4\}$, or $\{6,3\}$. Formed by triangles, squares, or hexagons, respectively, these animals are also more commonly known as polyiamonds, polyominoes, and polyhexes in the literature.

In 1976 [8], Harary and Harborth studied extremal animals in the three Euclidean cases. More specifically, they gave algebraic expressions and bounds for the number of interior, exterior, and total numbers of both vertices and edges that an animal with a fixed number of tiles can have. Then, they constructed a family of spiral animals that attain optimal values. Here, we extend Harary and Harborth’s analysis to extremal hyperbolic animals. First, we define and analyze analogous sequences of spiral $\{p,q\}$-animals for $(p-2)(q-2) \ge 4$ and provide algebraic expressions for the number of vertices and edges in terms of a particular recursive sequence of integers. Then, we prove that these spiral $\{p,q\}$-animals are indeed extremal. As a corollary of our results, we recover the formulas derived in [8] for the Euclidean cases.

We also explore the enumeration of extremal hyperbolic animals. Exact enumeration of $\{p,q\}$-animals is only known for a few $\{p,q\}$ pairs, and even then only for animals with a very small number of tiles. For instance, the number of $\{4,4\}$-animals with n tiles is only known for $n \le 56$ [13]; and otherwise, very little is known (see, for example, the entries of the OEIS A001207, A001420, A000228, A000577, A119611 [28] for values in the $\{3,6\}$-, $\{6,3\}$-, and $\{4,5\}$-tessellations). Though for Euclidean and some hyperbolic tessellations, there are asymptotic results and computational approximations that give a better understanding of the problem of animal enumeration [1, 2, 19, 24, 27].

In their closing thoughts in [8], Harary and Harborth raised the question of enumeration of extremal animals with n tiles. Surprisingly, this problem has remained largely unexplored, and it has been completely solved only for $\{4,4\}$-animals [17]. Before now, nothing was known about the enumeration of extremal hyperbolic animals. As a consequence of our main results, for all $\{p,q\}$, we find special sequences of extremal animals that are unique extremal animals, in the sense that any animal with the same number of tiles that is distinct up to isometries cannot be extremal (Fig. 1).

1.1 Main Results

We begin by analyzing a sequence of layered animals, which we use as benchmarks for computing extremal values. These layered animals will attain extremal values, but more significantly they provide context for keeping track of how each subsequent tile affects all of the graph parameters in play.

Remark 1.1

Note that in a $\{p,q\}$-animal, a vertex can have up to q incident tiles. If a vertex has fewer than q incident tiles, it is a perimeter vertex. If it has a complete set of q incident tiles, it is an interior vertex, and we say it is saturated. If an animal has holes, where a hole is defined to be a finite component of the complement of the animal, then the vertices bounding these holes are perimeter vertices. Also, note that an edge can have up to 2 tiles incident to it. If it has 2 faces, we call it an interior edge, and if it has 1 tile incident to it, we call it a perimeter edge.

Definition 1.2

We denote by $A_{p,q}(1)$ the animal with only one p-gon. We construct $A_{p,q}(k)$ from $A_{p,q}(k-1)$ by adding precisely the tiles needed to saturate all perimeter vertices of $A_{p,q}(k-1)$. The new tiles are called the k-th layer of the structure. We call $A_{p,q}(k)$ the complete k-layered $\{p,q\}$-animal.

Fig. 1

Left: $A_{p,q}(3)$ for $\{p,q\}=\{4,4\}$. Right: $A_{p,q}(3)$ for $\{p,q\}=\{4,5\}$. The degree of each perimeter vertex—the number of edges that are incident to the vertex—is written next to it. The case $\{4,5\}$ is hyperbolic, and it is drawn in the Poincaré disk

Theorem 1.3

Denote by ${\check{v}}(k)$, ${\check{e}}(k)$, and ${\check{n}}(k)$ the number of vertices, edges, and tiles, respectively, of the complete k-layered $\{p,q\}$-animal $A_{p,q}(k)$. Let $t=(p-2)(q-2)-2$ and $\alpha =\frac{t+\sqrt{t^2-4}}{2}$, then for all $k\ge 1$, we have the following equations in the Euclidean and hyperbolic cases, respectively.

• (i) For t=2, we have Euclidean animals, and they satisfy

  $$\begin{aligned} {\check{v}}(k)&= p k^2, \\ {\check{e}}(k)&= pk \left( \frac{q}{2}k-\frac{q}{2}+1\right) , \\ {\check{n}}(k)&= 1+ \frac{p(q-2)}{2}k^2 - \frac{p(q-2)}{2}k. \end{aligned}$$

• (ii) For $t>2$, we have hyperbolic animals, and they satisfy

  $$\begin{aligned} {\check{v}}(k)&= \frac{p}{t-2} \left( \alpha ^k+ \frac{1}{\alpha ^k} -2\right) , \\ {\check{e}}(k)&= \frac{p}{(\alpha -1)\sqrt{t^2-4}} \left( (\alpha +q-1)\alpha ^k+\frac{\alpha q -\alpha +1}{\alpha ^k} - q(\alpha +1) \right) , \\ {\check{n}}(k)&= 1 + \frac{p(q-2)}{(\alpha -1)\sqrt{t^2-4}} \left( \alpha ^k + \frac{1}{\alpha ^{k-1} } -\alpha -1 \right) . \end{aligned}$$

For $t >2$, we also find algebraic expressions in Eq. (3.4) for the following graph parameters: the number of interior vertices, perimeter edges, and interior edges of $A_{p,q}(k)$, denoted, respectively, by ${\check{v}}_{int}(k)$, ${\check{e}}_1(k)$, ${\check{e}}_2(k)$.

The equations in (i) of Theorem 1.3 for the Euclidean cases can also be derived from the results in [8]. While the techniques in that paper are specific to Euclidean animals, our methods here work for all animals living in both the Euclidean and hyperbolic planes. In the hyperbolic cases, we get as a corollary that the parameters of $A_{p,q}(k)$ grow exponentially; as expected from the properties of hyperbolic geometry. The exponential growth rate of these parameters is governed by the constant $\alpha >1$.

Corollary 1.4

Let $t=(p-2)(q-2)-2\ge 2$ and $\alpha =\frac{t+\sqrt{t^2-4}}{2}$. Then

$$\begin{aligned} \lim _{k \rightarrow \infty } \root k \of {{\check{v}}(k)} = \lim _{k \rightarrow \infty }{\check{v}}(k+1)/{\check{v}}(k) = \alpha , \end{aligned}$$

and the same limit is true for each of the graph parameters listed in Theorem 1.3.

Some of the recursive formulas for the complete layered sequence $A_{p,q}(k)$ in Theorem 1.3 were independently computed and used as a tool for understanding geometric and combinatorial properties of the $\{p,q\}$-tessellations. However, the extremality of these values was not previously examined.

For instance, in [10], Higuchi and Shirai use the layered $A_{p,q}(k)$ structures to compute the Cheeger constant of the infinite graph of the $\{p,q\}$-tessellations. Specifically, they give recursive computations for ${\check{v}}(k)$ and a value equivalent to the number of tiles in a layer, i.e., ${\check{n}}(k)-{\check{n}}(k-1)$. Using these values, they proved that the Chegeer constant of the $\{p,q\}$-tessellation, defined by

$$\begin{aligned} \inf \left\{ \frac{|E(\partial _v W)|}{\text {vol}(W)} : W \text { is a finite subgraph} \right\} , \end{aligned}$$

is equal to the limit of the corresponding values for $A_{p,q}(k)$ as $k\rightarrow \infty$. Here, $|E(\partial _v W)|$ is the number of edges connecting W with its complement, and vol$(W)=\sum _{x\in W} deg(x)$.

The $A_{p,q}(k)$ serve as a discrete analog of balls of radius k centered at $A_{p,q}(1)$, where we consider two faces to be adjacent if their intersection is non-empty. More commonly, proper combinatorial balls with respect to edge-distance $d(\cdot ,\cdot )$ in a graph with vertex set V are defined as ${\mathcal {B}}_k(x)=\{y\in V : d(x,y)\le k\}$. Then, viewing the ${\mathcal {B}}_k(x)$ as a structure on the dual graph of an animal, the definitions of $A_{p,q}(k)$ and ${\mathcal {B}}_k(x)$ coincide when $q=3$, since every face in the kth layer is necessarily glued along an edge to a face of $A_{p,q}(k-1)$. However, when $q\ge 4$, there will always be new faces only glued to the previous layer at a vertex, and ${\mathcal {B}}_k(x)$ will correspond to a sub-animal of $A_{p,q}(k)$.

In [15], Keller and Peyerimhoff compute the perimeter of these combinatorial balls ${\mathcal {B}}_k(x)$. These values are then used to find the exponential growth of the graph, defined as

$$\begin{aligned} \mu = \limsup _{k\rightarrow \infty } \frac{\log \text {vol} ({\mathcal {B}}_k(x)) }{k}. \end{aligned}$$

They obtain $\mu = \tau + \sqrt{\tau ^2-1}$ for the $\{p,q\}$-tessellation, where $\tau =q-\frac{2}{p-2}$. This value is related to our $t=(p-2)(q-2)-2$ by $\tau =\frac{t}{p-2}+2$. Moreover, Theorem 1.3 can be stated in terms of the combinatorial curvature at a vertex of a $\{p,q\}$-tessellation, given by $\kappa = 1-\frac{q}{2}+\frac{q}{p} = \frac{2-t}{2p}$. For references on combinatorial curvature, see [7, 11, 29].

In [25], Mertens and Moore find recursive formulas for the number of vertices and tiles on the sequence $A_{p,q}(k)$ to sample a certain type of random hyperbolic $\{p,q\}$-animals that allows them to give computational estimates of hyperbolic percolation thresholds on $\{p,q\}$-tessellations.

Instead of relying on these independent and related works, we give a complete proof of Theorem 1.3 to keep the discussion self-contained. In addition, our analysis is aimed at a more detailed description of the perimeter structure of $A_{p,q}(k)$, which we use to compute the graph parameters of all extremal n-tile $\{p,q\}$-animals.

After proving Theorem 1.3, we construct and analyze a sequence of spiral animals with n tiles, of which the complete k-layered animals are a subsequence. These $\{p,q\}$-spirals are denoted by $S_{p,q}(n)$ and are constructed in roughly the following way: find the maximum k, such that ${\check{n}}(k) \le n$, then attach $n-{\check{n}}(k)$ adjacent tiles in one direction along the boundary of $A_{p,q}(k)$, saturating perimeter vertices one a time along the way. The definition of the sequence $S_{p,q}(n)$ is made more precise in Definition 4.1 (see Fig. 2).

Before discussing the spirals in more detail, we pause here for a minute to point out the subtleties in the deluge of notation and bookkeeping we employ to keep track of all the parameters we are interested in.

Definition 1.5

We use variations on the notation v, e, and n, with some necessary subindices, to discuss graph parameters in three distinct settings.

• (1) First, we have the parameters of $A_{p,q}(k)$, presented in Theorem 1.3. These take input values in terms of k, and use adorned versions of the letters v, e, and n, e.g., ${\check{v}}(k)$, ${\check{e}}(k)$, ${\check{e}}_1(k)$, ${\check{v}}_{int}(k)$, etc.

• (2) For a general $\{p,q\}$-animal A or its underlying graph, we use unadorned notation and input the animal’s name, e.g., v(A), e(A), $e_1(A)$, $v_{int}(A)$, etc.

• (3) For the spiral $S_{p,q}(n)$, we use unadorned letters and the tile number n as the input, e.g., $v(n) = v\left( S_{p,q}(n)\right) , e(n) = e\left( S_{p,q}(n)\right) , e_1(n) = e_1\left( S_{p,q}(n)\right)$, $v_{int}(n) = v_{int}\left( S_{p,q}(n)\right)$, etc.

For the spiral $S_{p,q}(n)$, we compute its parameters in terms of the sequence of vertex degrees on the perimeter of the previous layer of the spiral. To accomplish this, it is useful to label the vertices on the perimeter of $A_{p,q}(k)$ by $x_{k,i}$ (see Definition 3.5), and to denote by $d_{k,i}$ the degree of $x_{k,i}$. The sequences $d_{k,i}$ are computed recursively at the end of Section 3.

Fig. 2

$S_{p,q}(n)$ for $n=37$ and $\{p,q\}=\{4,5\}$. $A_{4,5}(2)$ is shown in dark gray. The light gray tiles are those necessary to complete $S_{4,5}(37)$. The growth of the spiral is depicted by the dotted lines. Big-dot points mark the beginning (in the counterclockwise direction) of the perimeter vertices on each layer; these are denoted by $x_{k,1}$. The number of perimeter vertices of $A_{4,5}(2)$ that are interior vertices of $S_{4,5}(37)$ is $m=9$; these vertices are marked by dashed circles. See [23] for our interactive applets to explore spiral animals and their graph parameters

Theorem 1.6

Fix $\{p,q\}$, such that $(p-2)(q-2)\ge 4$. Let $S_{p,q}(n)$ be the $\{p,q\}$-spiral with n tiles, and let k be such that ${\check{n}}(k)< n < {\check{n}}(k+1)$. Let m count the number of perimeter vertices of $A_{p,q}(k)$ that are saturated in $S_{p,q}(n)$. Then

$$\begin{aligned} e(n)&= (p-1)(n-{\check{n}}(k))+{\check{e}}(k)-m, \\ v(n)&= (p-2)(n-{\check{n}}(k))+{\check{v}}(k)-m. \\ e_1(n)&= (p-2)(n-{\check{n}}(k)) + {\check{e}}_1(k)-2m. \end{aligned}$$

Furthermore, m can be computed as follows: If $n-{\check{n}}(k)\le q-d_{k,1}$, then $m=0$. And otherwise, m takes the unique value $\ge 1$, such that

$$\begin{aligned} \sum _{i=1}^m (q-d_{k,i}) \le n-{\check{n}}(k)-1 < \sum _{i=1}^{m+1} (q-d_{k,i}). \end{aligned}$$

(1.7)

The next theorem states that the spirals in fact attain extremal values in the graph parameters listed above. It is natural to imagine that this should be the case, as the spiral configuration intuitively has the effect of wrapping up as many vertices and edges in the interior as possible, where they can be shared by most tiles. Thus, interior parameters are maximized, while perimeter and overall counts are minimized.

Theorem 1.8

Fix $\{p,q\}$, such that $(p-2)(q-2)\ge 4$, and let A be a $\{p,q\}$-animal with n tiles. Then, $e_2(A)$ and $v_{int}(A)$ are maximized, and $e_1(A)$, e(A), and v(A) are minimized when $A=S_{p,q}(n)$.

Euclidean spiral-like animals have also been used by Buchholz and de Launey [6] for exploring the extremal combinatorial problem of edge minimization for certain families of animals that do not tessellate the Euclidean plane. They use spiral-like arrangements to obtain asymptotic results for extremal values on the number of internal edges. In that setting, it remains open as to whether these spiral-like arrangements are actually extremal, that is, if they attain and provide the exact minimal optimal values for the number of internal edges.

Theorem 1.8 shows that the minimum perimeter attainable by a $\{p,q\}$-animal with n tiles, which we denote by ${\mathcal {P}}_{p,q}(n)$, is equal to $e_1(n)$. Plugging the Euclidean $\{p,q\}$ values into Theorem 1.6, we recover Harary and Harborth’s formulas for extremal values of animals on regular tessellations of the Euclidean plane [8].

Corollary 1.9

For $\{p,q\}=\{3,6\}$, $\{4,4\}$, and $\{6,3\}$, we have

$$\begin{aligned} {\mathcal {P}}_{3,6}(n)&= 2 \left\lceil \frac{1}{2}( n+\sqrt{6n}) \right\rceil - n, \\ {\mathcal {P}}_{4,4}(n)&= 2 \left\lceil 2\sqrt{n} \right\rceil , \\ {\mathcal {P}}_{6,3}(n)&= 2 \left\lceil \sqrt{12n-3} \right\rceil . \end{aligned}$$

While the Euclidean cases yield closed formulas, in the hyperbolic case, it remains an open problem to find a closed formula for ${\mathcal {P}}_{p,q}$ in terms of the number of tiles.¹

Finally, we address the problem of enumerating extremal n-tile animals for a fixed n, exhibiting several sequences which give unique extremal animals up to isometries. The question of counting extremal animals was first posed by Harary and Harborth in [8]. In the $\{4,4\}$ case [17], Kurz proved that squares and pronic rectangles, i.e., polyominoes with $l^2$ tiles and rectangles with $l(l+1)$ tiles for $l\ge 1$, respectively, are unique extremal animals up to isometries. Here, we find sequences of $\{p,q\}$-animals which generalize this result for all $\{p,q\}$ pairs in Theorems 6.3 and 6.4 .

The rest of the paper is structured as follows: In Sect. 2, we set up notation and discuss graph theoretic formulae we will need later on. In Sect. 3, we analyze the layered animals $A_{p,q}(k)$, we deduce formulas for their parameters to prove Theorem 1.3, and we write the substitution rules necessary to construct their perimeter sequence of vertex degrees $d_{k,i}$. We conclude Sect. 1.3 with detailed examples that highlight the difference between the Euclidean and hyperbolic cases. Then, in Sect. 4, we prove Theorem 1.6 by finding algebraic expressions for the parameters of $S_{p,q}(n)$ in terms of the sequences $d_{k,i}$. In Sect. 5, we provide the proof of Theorem 1.8 which states that spirals are indeed extremal. In Sect. 6, we prove Theorems 6.3 and 6.4 regarding unique extremal animals. And finally, in Sect. 7, we state open problems and give concluding remarks.

2 Definitions and Preliminary Results

Consider a $\{p,q\}$-animal A. The edges and vertices of the p-gons of A define a planar graph, which we will refer to as the underlying graph of A. Here, and throughout this paper, we use the term faces only to refer to the bounded faces of a planar graph. Recall that a hole in an animal is defined to be a finite component of the complement of the animal. Therefore, if A has no holes, then the number of tiles of A is equal to the number of faces of its underlying graph, each of which is a p-gon in the $\{p,q\}$-tessellation. Thus, for convenience, when an animal A has no holes, we conflate the notation for these structures and denote its underlying graph also by A.

There is also the dual of an animal A, which we denote by $A'$. The dual of an animal is the planar graph constructed by placing a vertex at each tile of the animal and connecting two vertices if and only if their corresponding tiles share an edge. More generally, given any planar graph G, its dual $G'$ is constructed by placing a vertex at each face of G and connecting two vertices if and only if their corresponding faces share an edge. Observe that if A is an animal with a hole, then that hole will correspond to a vertex in the dual of A’s underlying graph, but not in the dual of A. However, when A is an animal with no holes, then the dual of A and the dual of its underlying graph are the same. When A is a $\{p,q\}$-animal, it is easy to see that its dual is a subgraph of the $\{q,p\}$-tessellation, and we will rely heavily on this duality to prove our results.

To begin, we restrict ourselves to animals with no holes, so that the dual of an animal and its underlying graph are always the same. Then, we extend our results to animals with holes as the last piece in proving Theorem 1.8. Of course, the dual of an animal is often merely a graph and not another animal. For instance, if A is a single tile, then its dual graph is a single vertex with no faces. To account for this, we consider a more general class of subgraphs of the $\{p,q\}$-tessellation which includes animals that do not have holes.

Definition 2.1

We call G a $\{p,q\}$-graph if G is a subgraph of the $\{p,q\}$-tessellation in which every bounded face has exactly p edges.

Every face of the underlying graph of a $\{p,q\}$-animal with no holes is a p-gon, and so, the underlying graph of such an animal is always a $\{p,q\}$-graph. Definition 2.1 crucially also allows for vertices and edges which do not bound faces.

For the rest of this paper, we always assume that $(p-2)(q-2)\ge 4$ for the pair $\{p,q\}$. We denote the total number of vertices, edges, and faces of a fixed $\{p,q\}$-graph G in the same manner as for a $\{p,q\}$-animal, using v(G), e(G), and n(G), respectively. Furthermore, we partition the vertices and edges by the number of incident edges and faces, respectively

$$\begin{aligned} v_i(G)&= \# \text { vertices of degree } i, \text { for } 1\le i \le q-1,\\ v_q(G)&= \# \text { vertices of degree }q\text { incident to at most }q-1\text { faces,}\\ v_{int}(G)&= \# \text { interior vertices, i.e., vertices of degree }q\text { incident to }q\text { faces,}\\ e_i(G)&= \# \text { edges incident to }i\text { faces, for } i = 0,1,2. \end{aligned}$$

All non-interior vertices are called perimeter vertices, and these are partitioned by the $v_i$ according to their degrees. Similarly, edges incident to at most 1 face are called perimeter edges, while edges incident to 2 faces are called interior edges.

When a fixed G is understood, we write simply v, e, n, etc, and for its dual graph $G'$, we write $v'$, $e'$, $n'$, etc. It is easily seen that when G is a $\{p,q\}$-graph, p, and q switch roles for $G'$, which is a $\{q,p\}$-graph. In general, $v'$, $e'$, and $n'$ can be counted directly by various parameters of G. We know by definition that $v' = n$; the edges of $G'$ correspond to edges of G which are incident to two faces of G, and hence, $e' = e_2$; and a face of $G'$ corresponds to an interior vertex of G, so $n' = v_{int}$. We further partition the edges of the dual graph and count its connected components

$$\begin{aligned} e_{2,i}(G)&= \# \text { edges in }G'\text { incident to }i\text { faces, for } i = 0,1,2,\\ c'(G)&= \# \text { connected components of }G'\text {.} \end{aligned}$$

Fig. 3

A $\{5,5\}$-animal and its dual. Its parameters are $n=13$, $e=50$, $e_1=36$, $e_2=14$, $v=38$, $v_{int}=2$, $e_{2,0}=5$, $e_{2,1}=8$ and $e_{2,2}=1$. Any resemblance to a real animal is pure coincidence; no animals were harmed for this research

For an animal, $c'$ is always 1 by definition. But here, we will obtain more general bounds for G a $\{p,q\}$-graph. Using Euler’s formula for $G'$, and also counting its edges with respect to incident faces, we have that

$$\begin{aligned} n-e_2+v_{int}&=c', \\ q\cdot v_{int}&= e_{2,1}+2e_{2,2} =e_2 -e_{2,0}+e_{2,2}. \end{aligned}$$

Combining these equations to eliminate $v_{int}$ yields

$$\begin{aligned} e_2 = \frac{q(n-c') -e_{2,0} +e_{2,2}}{q-1}. \end{aligned}$$

(2.2)

This formula will allow us to use induction to prove that $e_2(G)\le e_2(S_{p,q}(n))$ for any $\{p,q\}$-graph with exactly n faces by translating the inequality to the dual graphs (Fig. 3).

We will also need the following lemma which asserts that the number of tiles decreases when we perform the dual operation. Observe that if a $\{p,q\}$-graph is a tree, that is a connected graph with no faces, then $v_{int}=0$, and the dual graph of that component is the empty graph. Thus, it is sufficient to only consider components with faces.

Lemma 2.3

Let G be a $\{p,q\}$-graph with $q\ge 4$, such that every connected component has at least one face. Then, $v_{int}\le n-1$. Moreover, if $q=3$, then $v_{int} \le 2n-2$, and if $q\ge 6$, then $v_{int}\le \left\lfloor \frac{n}{2} \right\rfloor$.

Proof

Let c be the number of connected components of G. The Handshake Lemma and Euler’s formula for G are

$$\begin{aligned} q \cdot v_{int} + \sum _{i=1}^q i\cdot v_i&= 2e, \\ v - e +n&= c. \end{aligned}$$

Using these equations to eliminate e, we obtain

$$\begin{aligned} (q-2)v_{int} + \sum _{i=1}^q (i-2)\cdot v_i = 2n-2c. \end{aligned}$$

The sum of $(i-2)\cdot v_i$ can be negative if $v_1 > 0$, and to avoid this we iteratively prune all degree 1 vertices, one at a time, until there are none left. Cycles in a graph cannot be deleted via this process; therefore, since each component is assumed to have at least one face, the resulting graph has the same number of faces, interior vertices, and connected components as G. Let ${\bar{v}}_i$ denote the corresponding parameters in the reduced graph, with ${\bar{v}}_1=0$. Then

$$\begin{aligned} (q-2)v_{int} \le (q-2)v_{int} + \sum _{i=2}^q (i-2)\cdot {\bar{v}}_i = 2n-2c \le 2n -2. \end{aligned}$$

This gives the desired bounds, choosing the appropriate q in each case. $\square$

3 Complete k-layered $\{p,q\}$-animals

In this section, we define and study the main properties of the complete k-layered $\{p,q\}$-animals $A_{p,q}(k)$. Recall from Definition 1.2 that $A_{p,q}(1)$ is the regular p-gon, and then, $A_{p,q}(k)$ is constructed inductively by attaching all allowable tiles to the perimeter of $A_{p,q}(k-1)$. The graph parameters of $A_{p,q}(k)$ are denoted by ${\check{v}}(k)$, ${\check{e}}(k)$, ${\check{n}}(k)$, etc.

As each new layer is added, these parameters can be tracked by characterizing the geometry of how individual tiles are attached. When adding a tile T to an animal A, we use the notation $\deg _{A}(T)$ to denote the number of edges T shares with A. This is, in fact, the degree of the vertex representing T in the dual graph of $A\cup T$. More informally, we describe a tile being added to a given animal as being $\epsilon$-glued to A if $\deg _{A}(T)=\epsilon$. In constructing $A_{p,q}(k)$ from $A_{p,q}(k-1)$, we consider each tile individually and examine $\deg _{A_{p,q}(k-1)}(T)$ for every tile T in the k-th layer. We will call $\epsilon$ the gluing parameter of the tile and use it to classify a layer’s perimeter vertices by degree, and then find recursive formulas in Proposition 3.1 for counting the number of vertices of each degree in a layer. The solution to these recursions will give exact formulas for the number of vertices of each degree in Lemma 3.3, and this information will then be used to prove the full set of formulas in Theorem 1.3 (Fig. 4).

Fig. 4

Here, we depict $A_{p,q}(k)$ for $\{p,q\}=\{3,7\}$ and $k=3$. Big-dot points mark the beginning of the perimeter vertices on each layer; these are denoted by $x_{k,1}$. The degree of each perimeter vertex of $A_{3,7}(3)$ is written next to it; this is the sequence $d_{3,i}$, starting at $x_{3,1}$ in the counterclockwise direction. See Fig. 1 for the cases $\{4,4\}$ and $\{4,5\}$

Proposition 3.1

Recall that perimeter vertices of $A_{p,q}(k)$ are counted by ${\check{v}}_i(k)$ according to their degree i. Therefore, ${\check{v}}_2(k)$, ${\check{v}}_3(k)$, and ${\check{v}}_4(k)$ are the number of perimeter vertices of $A_{p,q}(k)$ of degree 2, 3, and 4, respectively. Then, for $p=3$ and $k\ge 3$, ${\check{v}}_i(k)=0$ for $i\ne 3,4$ and

$$\begin{aligned} {\check{v}}_3(k)&= (q-5){\check{v}}_3(k-1) + (q-6){\check{v}}_4(k-1), \\ {\check{v}}_4(k)&= {\check{v}}_3(k-1) + {\check{v}}_4(k-1). \end{aligned}$$

For $p\ge 4$ and $k\ge 2$, ${\check{v}}_i(k)=0$ for $i\ne 2,3$ and

$$\begin{aligned} {\check{v}}_2(k)&=\left( (p-3)(q-2)-1 \right) {\check{v}}_2(k-1) + \left( (p-3)(q-3)-1 \right) {\check{v}}_3(k-1), \\ {\check{v}}_3(k)&= (q-2) {\check{v}}_2(k-1) + (q-3) {\check{v}}_3(k-1). \end{aligned}$$

Proof

We begin by noting that when a tile is glued on in the k-th layer, its set of glued edges and vertices must form a connected path. If not, the resulting topological handle would break the q-fold symmetry of the tessellation at any perimeter vertex of $A_{p,q}(k-1)$ in the hole created. Furthermore, a perimeter vertex of degree d will be incident to $d-1$ tiles of $A_{p,q}(k-1)$, since it has two perimeter edges, and each additional edge divides the incident faces in the $(k-1)$th layer into an additional tile. En route to proving the recursions, we will use this distinction to inductively prove that when $p=3$, all vertices have degree 3 or degree 4, and when $p\ge 4$, all vertices have degree 2 or degree 3.

Suppose that $q\ge 4$. In building $A_{p,q}(2)$, each edge of the single tile in $A_{p,q}(1)$ has a distinct tile glued to it in the second layer, and thus, these tiles are each 1-glued to $A_{p,q}(1)$. Each vertex of $A_{p,q}(1)$ needs $q-3\ge 1$ additional tiles glued in at the corners to become saturated, and each of these corner tiles is 0-glued. Note that a 0-glued tile has one edge glued to each of the tiles next to it in the 2nd layer, while a 1-glued tile contributes three interior edges, one glued to $A_{p,q}(1)$ and the other two to its neighbors in the 2nd layer. This observation is also true when attaching tiles to $A_{p,q}(k-1)$ to form the kth layer. That is: a 0-glued tile has one edge glued to each of the tiles next to it in the kth layer, while a 1-glued tile contributes three interior edges, one glued to $A_{p,q}(k-1)$ and the other two to its neighbors in the kth layer. Thus, when $p=3$, a 1-glued tile leaves a single “apex” vertex on the perimeter, while a 0-glued tile has a single perimeter edge. In this case, the apex vertex of a 1-glued tile is flanked by two 0-glued tiles and has degree 4, while any other perimeter vertex must be at the joint of two 0-glued tiles, and thus has degree 3. When $p\ge 4$, both 1-glued and 0-glued tiles have at least one perimeter edge. Therefore, a perimeter vertex can be at the joint of two adjacent tiles, in which case it has degree 3, or it can belong to a single tile, in which case it has degree 2 (Fig. 5).

Fig. 5

Right When $p,q\ge 4$, each vertex of degree $=3$ in $A_{p,q}(k-1)$ contributes to $q-3$ vertices of degree $=3$ in $A_{p,q}(k)$, and $(q-3)(p-3)-1$ vertices of degree $=2$. Left When $p=3$, each vertex of degree $d=3$ or 4 in $A_{p,q}(k-1)$, contributes to a vertex of degree $=4$ in $A_{p,q}(k)$ and $q-d-2$ vertices of degree $= 3$

Now, for some $k\ge 2$, suppose these are the only possible vertex degrees in either case for the perimeter vertices of $A_{p,q}(k-1)$, and consider constructing $A_{p,q}(k)$ from $A_{p,q}(k-1)$. For each perimeter vertex x of degree d, we must attach $q-d+1$ tiles to x. To avoid overlap, we associate to x only the first $q-d$ tiles in the counterclockwise direction, which is also the number of additional edges it needs to become saturated. Note that when $p=3$, we have that $q\ge 6$ and $q-d\ge 2$, and when $p\ge 4$, we have that $q-d\ge 1$. In particular, every perimeter vertex needs at least one additional edge. And since glued edges form connected paths on the perimeter, a gluing parameter of 2 or more would cover at least one vertex and obstruct it from getting additional edges. Therefore, all tiles are either 1-glued or 0-glued to $A_{p,q}(k-1)$, and every perimeter edge of $A_{p,q}(k-1)$ has a distinct 1-glued tile attached to it. When $p\ge 4$, this immediately yields the same circumstances as in the second layer, and therefore, all vertices have degree 2 or 3. When $p=3$, we only need to confirm that 1-glued tiles are not adjacent. But here, we have that $q-d\ge 2$, so in addition to the tile 1-glued to the perimeter edge which has x as its further counterclockwise vertex, there must be at least one 0-glued tile before the next 1-glued tile. Thus, we have the same situation as in the second layer, and all vertices are degree 3 or 4.

The above analysis also shows us how to count vertices of each degree, as depicted in Fig. 5. Fix $p=3$, and once again, let x be a perimeter vertex of $A_{p,q}(k-1)$ of degree d. The first tile is always 1-glued to $A_{p,q}(k-1)$, while the remaining $q-d-1\ge 1$ are 0-glued at x. Therefore, the first tile contributes one perimeter vertex of $A_{p,q}(k)$ of degree 4, and the next $q-d-2$ tiles each contribute one vertex of degree 3. The last tile associated with x does not add to this count, as it shares one perimeter vertex with the previous tile associated with x, and the other with the 1-glued tile whose perimeter vertex is counted by the next perimeter vertex of $A_{p,q}(k)$. In summary, all perimeter vertices of $A_{p,q}(k-1)$ of degree 3 contribute in total to $(q-5){\check{v}}_3(k-1)$ perimeter vertices of $A_{p,q}(k)$ of degree 3 and ${\check{v}}_3(k-1)$ vertices of degree 4. Similarly, perimeter vertices of $A_{p,q}(k-1)$ of degree 4 contribute to $(q-6){\check{v}}_4(k-1)$ perimeter vertices of $A_{p,q}(k)$ of degree 3 and ${\check{v}}_4(k-1)$ vertices of degree 4. By adding these two contributions, we arrive at the recurrence formulas for $p=3$.

The case for $p\ge 4$ is similar, starting with x a perimeter vertex of $A_{p,q}(k-1)$ of degree d. Recall that a 1-glued tile has three interior edges, and thus two interior vertices, while a 0-glued tile has two interior edges and one interior vertex. Therefore, the initial 1-glued tile has $p-2$ perimeter vertices, and the following 0-glued tiles each have $p-1$, but we ignore the last one in a counterclockwise direction from each tile to avoid overlap. The first of the $q-d$ tiles added at x has one vertex of degree 3 and $p-4$ of degree 2. For the rest of the tiles, each one contributes one perimeter vertex of $A_{p,q}(k)$ of degree 3, which is incident to the adjacent tile in the clockwise direction, and $p-3$ vertices of degree 2. In summary, a perimeter vertex of $A_{p,q}(k-1)$ of degree d contributes $q-d$ vertices of degree 3 to $A_{p,q}(k)$ and $(q-d)(p-3)-1$ vertices of degree 2. This gives the recurrence relations for $p\ge 4$.

Finally, consider the case that $q=3$. Note that all vertices on tiles have a degree of at least 2, and no tile can have degree more than q, so trivially all vertices have degrees 2 or 3. In this case $q-3=0$, so there are no 0-glued corner tiles in the second layer, and we add to our induction the assumption that no tile in $A_{p,q}(k-1)$ is $\epsilon$-glued for $\epsilon \ge 3$. Then, $q-d=1$ when $d=2$, and $q-d=0$ when $d=3$. We can understand this by associating to every perimeter vertex the tile which is glued along its incident edge in the clockwise direction unless another vertex’s tile is already attached there. Here, vertices of degree 3 already have all of their edges, so the tile glued to its counterclockwise edge, associated with the adjacent vertex in that direction, must also saturate it. This requires that no degree 3 vertices are adjacent. However, since no tile is more than 2-glued, accounting for four interior edges, and $p\ge 6$, every tile in the $(k-1)$-th layer must have at least one perimeter vertex, which has degree 2. Therefore, there are no adjacent degree 3 vertices, and each degree 3 vertex is saturated by the tile associated with the adjacent vertex of degree 2 in the counterclockwise direction. The recursions are then the same as for $p\ge 4$, where $(q-d)(p-3)-1=-1$ comes from the fact that a vertex of degree 3 siphons off an edge from the tile associated with the adjacent degree 2 vertex, removing one degree 2 vertex from the perimeter. $\square$

This proof also elucidates a number of important details about the gluing parameters, which we collect here for convenience.

Remark 3.2

If $q = 3$, then all tiles in $A_{p,q}(k)$ are either 1-glued or 2-glued to $A_{p,q}(k-1)$, with one 2-glued tile for every vertex of degree 3 in $A_{p,q}(k-1)$. If $q \ge 4$, every tile is either 0-glued or 1-glued, with a distinct 1-glued tile attached to each perimeter edge of $A_{p,q}(k-1)$.

Lemma 3.3

Let $t=(p-2)(q-2)-2$ and $\alpha =\frac{t+\sqrt{t^2-4}}{2}$, $\beta =\frac{t-\sqrt{t^2-4}}{2}$. The solution to the recurrence relations of Proposition 3.1 is

• (1) When $t=2$, we have the Euclidean cases:

  $$\begin{aligned} \text {For } \{p,q\}=&\,\{3,6\}, \, k\ge 2,&\text {For } \{p,q\}=&\, \{4,4\}, k\ge 1,&\text {For }\{p,q\}=&\,\{6,3\}, k\ge 1, \\ {\check{v}}_3(k)&= 6,&{\check{v}}_2(k)&= 4,&{\check{v}}_2(k)&= 6k,\\ {\check{v}}_4(k)&= 3+6(k-2),&{\check{v}}_3(k)&=8(k-1) ,&{\check{v}}_3(k)&= 6(k-1). \end{aligned}$$

• (2) For $p=3$, $q>6$, and $k\ge 2$

  $$\begin{aligned} {\check{v}}_3(k)&=\frac{3}{\alpha -\beta } \left( (\alpha -1)(q-3-\beta )\alpha ^{k-2} + (1-\beta )(q-3-\alpha )\beta ^{k-2} \right) , \\ {\check{v}}_4(k)&= \frac{3}{\alpha -\beta } \left( (q-3-\beta )\alpha ^{k-2} - (q-3-\alpha )\beta ^{k-2} \right) . \end{aligned}$$

• (3) For $p\ge 4$, $(p-2)(q-2)>4$, and $k\ge 1$

  $$\begin{aligned} {\check{v}}_2(k)&=\frac{p}{\alpha -\beta } \left( -(q-3-\alpha )\alpha ^{k-1} + (q-3-\beta )\beta ^{k-1} \right) , \\ {\check{v}}_3(k)&= \frac{p}{\alpha -\beta } \left( (q-2)\alpha ^{k-1} - (q-2)\beta ^{k-1} \right) . \end{aligned}$$

Proof

The equations in (1) can also be derived from the results in [8]. For completeness, we prove them here using our present techniques. Namely, we solve a linear system of $2\times 2$ recurrence relations; the associated matrix in both cases has determinant 1 and trace $t=(p-2)(q-2)-2$. The characteristic polynomial is then $x^2-tx+1$, and its roots are $\alpha$ and $\beta$.

When $t=2$, we have $\alpha =\beta =1$, and the growth is linear. When $t>2$, we get exponential growth in terms of $\alpha$ and $\beta$. The initial conditions are ${\check{v}}_3(2)=3(q-4)$, ${\check{v}}_4(2)=3$ for $p=3$, and ${\check{v}}_2(1)=p$, ${\check{v}}_3(1)=0$ for $p\ge 4$. The diagonalization matrix is

$$\begin{aligned} M = \begin{pmatrix} 1-\alpha &{} 1-\beta \\ -1 &{} -1 \end{pmatrix} \text{ for } p=3, \text { or } M=\begin{pmatrix} \frac{q-3-\alpha }{q-2} &{} \frac{q-3-\beta }{q-2} \\ -1 &{} -1 \end{pmatrix} \text{ for } p\ge 4. \end{aligned}$$

The kth element of the sequences can be computed from

$$\begin{aligned} \begin{pmatrix} {\check{v}}_3(k) \\ {\check{v}}_4(k) \end{pmatrix} = M \begin{pmatrix} \alpha ^{k-2} &{} 0 \\ 0 &{} \beta ^{k-2} \end{pmatrix} M^{-1} \begin{pmatrix} {\check{v}}_3(2) \\ {\check{v}}_4(2) \end{pmatrix}, \text { for }p=3\text {,} \end{aligned}$$

$$\begin{aligned} \begin{pmatrix} {\check{v}}_2(k) \\ {\check{v}}_3(k) \end{pmatrix} = M \begin{pmatrix} \alpha ^{k-1} &{} 0 \\ 0 &{} \beta ^{k-1} \end{pmatrix} M^{-1} \begin{pmatrix} {\check{v}}_2(1) \\ {\check{v}}_3(1) \end{pmatrix}, \text { for } p\ge 4. \end{aligned}$$

From these, we obtain the desired expressions. $\square$

Proof of Theorem 1.3

First, we work the case $p\ge 4$. The vertices of $A_{p,q}(k)$ consists of its perimeter plus those of $A_{p,q}(k-1)$, that is, ${\check{v}}(k)={\check{v}}(k-1)+{\check{v}}_2(k)+{\check{v}}_3(k)$, then

$$\begin{aligned} {\check{v}}(k) = \sum _{j=1}^k {\check{v}}_2(j) + {\check{v}}_3(j). \end{aligned}$$

As the perimeter of $A_{p,q}(k)$ is a cycle, then ${\check{e}}_1(k)={\check{v}}_2(k)+{\check{v}}_3(k)$. Next, ${\check{e}}_2(k)$ consists of the interior and perimeter edges of $A_{p,q}(k-1)$, plus the interior edges of $A_{p,q}(k) \setminus A_{p,q}(k-1)$, which also correspond to the edges that connect perimeter vertices of $A_{p,q}(k-1)$ and $A_{p,q}(k)$. The latter are precisely $q-d$ for each vertex of degree d in the perimeter of $A_{p,q}(k-1)$. Then, ${\check{e}}_{2}(k)={\check{e}}_2(k-1)+{\check{e}}_1(k-1)+(q-2){\check{v}}_2(k-1) + (q-3){\check{v}}_3(k-1)={\check{e}}_2(k-1)+(q-1){\check{v}}_2(k-1)+(q-2){\check{v}}_3(k-1)$. Now, recalling that ${\check{e}}_2(1)=0$, we get

$$\begin{aligned} {\check{e}}_2(k)= (q-1)\sum _{j=1}^{k-1}{\check{v}}_2(j) + (q-2)\sum _{j=1}^{k-1}{\check{v}}_3(j). \end{aligned}$$

Finally, ${\check{e}}(k)={\check{e}}_1(k)+{\check{e}}_2(k)$ and ${\check{n}}(k)=1-{\check{v}}(k)+{\check{e}}(k)$. All the previous, together with the expressions for ${\check{v}}_2(k)$ and ${\check{v}}_3(k)$, give us the formulas for Theorem 1.3. We just have to notice that $\beta =\alpha ^{-1}$, $\alpha +\beta =t$, and $\alpha -\beta =\sqrt{t^2-4}$.

The case for $p=3$ is analogous. In this case, ${\check{v}}_3(1) = {\check{v}}_4(1) = 0$, and the coefficients before the summations are $q-2$ and $q-3$, respectively. Moreover, since $k\ge 2$, we need to consider the interior edges already present in $A_{p,q}(2)$. Summarizing, we have

$$\begin{aligned} {\check{e}}_2(k)= 3q-3 + (q-2)\sum _{j=2}^{k-1}{\check{v}}_3(j) + (q-3)\sum _{j=2}^{k-1}{\check{v}}_4(j). \end{aligned}$$

Here, we collect the formulas for $A_{p,q}(k)$ in the hyperbolic case, $(p-2)(q-2)>4$ for all $k\ge 1$

$$\begin{aligned} \begin{aligned} {\check{n}}(k)&= 1 + \frac{p(q-2)}{(\alpha -1)\sqrt{t^2-4}} \left( \alpha ^k + \frac{1}{\alpha ^{k-1} } -\alpha -1 \right) \\ {\check{v}}(k)&= \frac{p}{t-2} \left( \alpha ^k+ \frac{1}{\alpha ^k} -2\right) \\ {\check{e}}(k)&= \frac{p}{(\alpha -1)\sqrt{t^2-4}} \left( (\alpha +q-1)\alpha ^k+\frac{\alpha q -\alpha +1}{\alpha ^k} - q(\alpha +1) \right) \\ {\check{e}}_1(k)&= \frac{p(\alpha +1)}{\sqrt{t^2-4}} \left( \alpha ^{k-1} -\frac{1}{\alpha ^k} \right) \\ {\check{e}}_2(k)&= \frac{p}{(\alpha -1) \sqrt{t^2-4}} \left( (\alpha q-\alpha +1) \alpha ^{k-1} + \frac{q-1+\alpha }{\alpha ^{k-1}} -q(\alpha +1) \right) \\ {\check{v}}_{int}(k)&= \frac{p}{t-2} \left( \alpha ^{k-1}+\frac{1}{\alpha ^{k-1}} -2\right) . \end{aligned} \end{aligned}$$

(3.4)

$\square$

Now, we establish how to construct the degree sequences. To begin with, we order the vertices on the boundary of $A_{p,q}(k)$, labeling them $x_{k,i}$ for $1\le i\le {\check{e}}_1(k)$, with $d_{k,i}=\deg _{A_{p,q}(k)}(x_{k,i})$.

Definition 3.5

For $A_{p,q}(1)$, label the vertices $x_{1,1},x_{1,2}, \dots , x_{1,p}$ in the counterclockwise direction. For $k\ge 2$, suppose that we have labeled the perimeter vertices of $A_{p,q}(k-1)$, and let T be the tile of $A_{p,q}(k)$ attached to both $x_{k-1,1}$ and $x_{k-1,{\check{e}}_1(k-1)}$, the first and last vertices of $A_{p,q}(k-1)$. Define $x_{k, 1}$ to be the vertex of T adjacent to $x_{k-1,{\check{e}}_1(k-1)}$, and different from $x_{k-1,1}$. Then, the perimeter vertices of $A_{p,q}(k)$ are labeled in the counterclockwise direction starting at $x_{k,1}$. See Figs. 2 and 4 .

Now, recall from the proof of Proposition 3.1 that each vertex in $A_{p,q}(k)$ generates vertices on the next layer according to its degree. Let $d_k$ denote the sequence $\{d_{k,i}\}$. We can compute the sequence $d_{k+1}$ from $d_k$ in the following manner. See Figs. 6, 7, and 8 .

First, $d_{1}$ is the sequence $2,2,\dots , 2$ containing p elements. Then, $d_{k}$ is constructed from $d_{k-1}$ by replacing the ith element $d_{k-1,i}$ with the string of the degrees of the perimeter vertices of $A_{p,q}(k)$ associated with $x_{k-1,i}$. More precisely: if $p\ge 4$ and $q\ge 4$, $d_{k-1,i}$ is replaced by

$$\begin{aligned} \underbrace{ \underbrace{3,2,\dots ,2}_{p-3}, \underbrace{3,2,\dots ,2}_{p-2}, \dots , \underbrace{3,2,\dots ,2}_{p-2} }_{q-d_{k-1,i} \text { groups of } 3,2,\dots ,2}. \end{aligned}$$

If $p=3$, and $q\ge 6$, $d_{k-1,i}$ is replaced by

$$\begin{aligned} \underbrace{4,3,\dots , 3}_{q-d_{k-1,i}-1}. \end{aligned}$$

Finally, if $q=3$, and $p\ge 6$, $d_{k-1,i}=2$ is replaced by

$$\begin{aligned} \underbrace{3,2,\dots ,2}_{p-3} \text { or } \underbrace{3,2,\dots ,2}_{p-4} \end{aligned}$$

depending on whether $d_{k-1,i}=2$ is preceded by $d_{k-1,i-1}=2$ or $d_{k-1,i-1}=3$, respectively. On the other hand, $d_{k-1,i}=3$ is simply erased.

Example 3.6

Here, we compute the sequences $d_k$ for the Euclidean cases and some hyperbolic ones. As expected, from Lemma 3.3, we will encounter linear growth in the former and exponential in the latter. In [23], we also provide an applet to explore hyperbolic animals and their parameters.

• A) For $\{p,q\}=\{3,6\}$, the substitution rules are: $4\rightarrow 4$; $3 \rightarrow 4,3$; and $2\rightarrow 4,3,3$. The first sequences are

  $$\begin{aligned} d_1&= 2,2,2&\\ d_2&= 4,3,3, \dots&(\text {3 times}) \\ d_3&= 4,4,3,4,3, \dots&(\text {3 times}) \\ d_4&= 4,4,4,3,4,4,3, \dots&(\text {3 times}). \end{aligned}$$

  It is easy to see that, for $k\ge 3$, $d_k$ consists of the sequence $\underbrace{4,4\dots , 4,3}_{k}\underbrace{4,4\dots , 4,3}_{k-1}$, repeated 3 times.

• B) For $\{p,q\}=\{3,7\}$, shown in Fig. 6, the substitution rules are: $4\rightarrow 4,3$; $3 \rightarrow 4,3,3$; and $2\rightarrow 4,3,3,3$. The first sequences are

  $$\begin{aligned} d_1&= 2,2,2&\\ d_2&= 4,3,3,3, \dots&(\text {3 times}) \\ d_3&= 4,3,4,3,3,4,3,3,4,3,3, \dots&(\text {3 times}) \\ d_4&= 4,3,4,3,3,4,3,4,3,3,4,3,3,4,3,4,3,3,4,3,3,4,3,4,3,3,4,3,3, \dots&(\text {3 times}). \end{aligned}$$

• C) For $\{p,q\}=\{4,4\}$, the substitution rules are: $3\rightarrow 3$, and $2 \rightarrow 3,3,2$. The first sequences are

  $$\begin{aligned} d_1&= 2,2,2,2&\\ d_2&= 3,3,2, \dots&(\text {4 times}) \\ d_3&= 3,3,3,3,2, \dots&(\text {4 times}) \\ d_4&= 3,3,3,3,3,3,2, \dots&(\text {4 times}). \end{aligned}$$

  It is easy to see that, for $k\ge 2$, $d_k$ consists of the sequence $\underbrace{3,3\dots , 3,2}_{2k-1}$, repeated 4 times.

• D) For $\{p,q\}=\{4,5\}$, shown in Fig. 7, the substitution rules are: $3 \rightarrow 3,3,2$, and $2\rightarrow 3,3,2,3,2$. The first sequences are

  $$\begin{aligned} d_1&= 2,2,2,2&\\ d_2&= 3,3,2,3,2, \dots&(\text {4 times}) \\ d_3&= 3,3,2,3,3,2,3,3,2,3,2,3,3,2,3,3,2,3,2, \dots&(\text {4 times}). \end{aligned}$$

• E) For $\{p,q\}=\{6,3\}$, the substitution rules are: 3 is erased; if a 2 is preceded by a 3, then $2 \rightarrow 3,2$; and if a 2 is preceded by a 2, then $2 \rightarrow 3,2,2$. The first sequences are

  $$\begin{aligned} d_1&= 2,2,2,2,2,2&\\ d_2&= 3,2,2, \dots&(\text {6 times}) \\ d_3&= 3,2,3,2,2, \dots&(\text {6 times}) \\ d_4&= 3,2,3,2,2,3,2,2, \dots&(\text {6 times}). \end{aligned}$$

  It is easy to see that, for $k\ge 2$, $d_k$ consists of the sequence $3,2,\underbrace{3,2,2,3,2,2,\dots , 3,2,2}_{3,2,2 \text { repeated } k-2 \text { times}}$, repeated 6 times.

• F) For $\{p,q\}=\{7,3\}$, shown in Fig. 8, the substitution rules are: 3 is erased; if a 2 is preceded by a 3, then $2 \rightarrow 3,2,2$; and if a 2 is preceded by a 2, then $2 \rightarrow 3,2,2,2$. The first sequences are

  $$\begin{aligned} d_1&= 2,2,2,2,2,2,2&\\ d_2&= 3,2,2,2, \dots&(\text {7 times}) \\ d_3&= 3,2,2,3,2,2,2,3,2,2,2 \dots&(\text {7 times}) \\ d_4&= 3,2,2,3,2,2,2,3,2,2,3,2,2,2,3,2,2,2,3,2,2,3,2,2,2,3,2,2,2, \dots&(\text {7 times}). \end{aligned}$$

Fig. 6

Graphic representation of the substitution rules for $\{p,q\}= \{3,7\}$. From $A_{3,7}(1)$ to $A_{3,7}(2)$, we apply $2\rightarrow 4,3,3,3$. From $A_{3,7}(2)$ to $A_{3,7}(3)$, we apply $3 \rightarrow 4,3,3$ and $4\rightarrow 4,3$. We observe that in this case, we only have vertices of degree two in $A_{3,7}(1)$, but then, all the vertices of $A_{3,7}(k)$ for $k>1$ will have degree 3 or 4

Fig. 7

Graphic representation of the substitution rules for $\{p,q\}= \{4,5\}$. From $A_{4,5}(1)$ to $A_{4,5}(2)$, we apply $2\rightarrow 3,3,2,3,2$; the associated tiles are shaded in light gray. We alternate the symbols $\blacktriangle$ and $\bullet$ to emphasize the substitution rules for each perimeter vertex of $A_{4,5}(2)$

Fig. 8

Graphic representation of the substitution rules for $\{p,q\}= \{7,3\}$. From $A_{7,3}(2)$ to $A_{7,3}(3)$, the 3 is erased (represented by $\times$), and $2 \rightarrow 3,2,2,2$. We alternate the symbols $\blacktriangle$ and $\bullet$ to emphasize the substitution rules of the vertices from the second layer to the next

4 $\{p,q\}$-Spiral Animals

In this section, we turn our attention to $\{p,q\}$-spiral animals, counting their graph parameters, and proving Theorem 1.6.

The $\{p,q\}$-spiral with n tiles will be denoted by $S_{p,q}(n)$. Recall that we refer to its graph parameters as $e(n), v(n), e_1(n)$, etc. The following procedure for constructing $S_{p,q}(n)$ gives the spiral in the counterclockwise direction, as seen in Fig. 2.

Definition 4.1

Let n be a positive integer. Then, $S_{p,q}(n)$ is constructed by adding tiles $T_1, T_2,\ldots , T_n$ one at a time, such that $T_n$ is the unique tile added to $S_{p,q}(n-1)$ to obtain $S_{p,q}(n)$. If $n={\check{n}}(k)$, then $S_{p,q}(n)=A_{p,q}(k)$. Otherwise, for ${\check{n}}(k)< n < {\check{n}}(k+1)$, first, $T_{{\check{n}}(k)+1}$ is attached to $A_{p,q}(k)$ by gluing it along the edge $\{x_{k,1}, x_{k,{\check{e}}_1(k)}\}$. Then, subsequent tiles $T_i$ are added by gluing along the perimeter edge of $T_{i-1}$ which contains $x_{k,1}$, until $x_{k,1}$ is saturated. Next, we move on to the vertex $x_{k,2}$, and we repeat this process until $n-{\check{n}}(k)$ tiles have been added to $A_{p,q}(k)$.

For the rest of this section, we always assume that ${\check{n}}(k) < n \le {\check{n}}(k+1)$, and thus, $T_n$ is a tile being added in the $(k+1)$th layer. Similar to $A_{p,q}(k)$, we use the gluing parameter $\epsilon$ of each subsequent tile to chart the jumps in the sequences $e_1(n)$ and $e_2(n)$. Here, $T_n$ is added to $S_{p,q}(n-1)$, and so, we say $T_n$ is $\epsilon$-glued if $\deg _{S_{p,q}(n-1)}(T_n)=\epsilon$, with $\epsilon \ge 1$, since $T_n$ always shares an edge with $T_{n-1}$.

Remark 4.2

If $T_n$ is $\epsilon$-glued to $S_{p,q}(n-1)$, then

$$\begin{aligned} e_1(n)-e_1(n-1)&= p-2 \epsilon ,\\ e_2(n)-e_2(n-1)&= \epsilon . \end{aligned}$$

This is a simple observation, as when $T_n$ is $\epsilon$-glued, it adds $p-\epsilon$ perimeter edges while covering $\epsilon$ edges of $S_{p,q}(n-1)$, and each covered edge is added to the count for $e_2$.

With $T_n$ in the $(k+1)$th layer, note that $\deg _{S_{p,q}(n-1)}(T_n)$ is easily determined from $\deg _{A_{p,q}(k)}(T_n)$, differing by either 0, 1, or 2 additional edges. The first tile $T_{{\check{n}}(k)+1}$ has no additional shared edges, while the last tile $T_{{\check{n}}(k+1)}$ has two additional shared edges; one with $T_{{\check{n}}(k+1)-1}$ and one with the first tile in this layer, $T_{{\check{n}}(k)+1}$. Otherwise, $T_n$ only shares one additional edge with $T_{n-1}$, and so, $\deg _{S_{p,q}(n-1)}(T_n)=\deg _{A_{p,q}(k)}(T_n)+1$. Combining this with the analysis in Proposition 3.1 and Remarks 3.2 and 4.2 , we can determine the exact values of these jumps.

Lemma 4.3

When $q > 3$ and $n > 1$

$$\begin{aligned}&e_1(n)-e_1(n-1) = p-2 \text { and } e_2(n)-e_2(n-1) = 1, \text { or }\\&e_1(n)-e_1(n-1) = p-4 \text { and } e_2(n)-e_2(n-1) = 2.\\ \end{aligned}$$

When $q=3$ and $n > 2$

$$\begin{aligned}&e_1(n)-e_1(n-1) = p-4 \text { and } e_2(n)-e_2(n-1) = 2, \text { or }\\&e_1(n)-e_1(n-1) = p-6 \text { and } e_2(n)-e_2(n-1) = 3.\\ \end{aligned}$$

Corollary 4.4

For $n \ge 1$ and $l\ge 1$, we have the bounds

$$\begin{aligned}&e_2(n+l)-e_2(n)\le 2l \text { when } q>3,\\&e_2(n+l)-e_2(n)\le 3l \text { when } q=3.\\ \end{aligned}$$

Proof of Theorem 1.6

Recall that $e_1(n)$ is the number of perimeter edges of $S_{p,q}(n)$, and m is the number of perimeter vertices of $A_{p,q}(k)$ which are saturated in $S_{p,q}(n)$.

When $T_n$ is $\epsilon$-glued, it saturates $\epsilon -1$ perimeter vertices of $A_{p,q}(k)$. Therefore, an $\epsilon$-glued tile increments m by $\epsilon -1$, and $e_1$ by $p-2\epsilon =(p-2)-2$(increment of m). Then, for any q, we get

$$\begin{aligned} e_1(n)= (p-2)(n-{\check{n}}(k)) + {\check{e}}_1(k) -2m, \end{aligned}$$

which gives the expression in Theorem 1.6. Similarly, we have

$$\begin{aligned} e_2(n)&= {\check{e}}_2(k) + n-{\check{n}}(k)+m, \\ e(n)&= (p-1)(n-{\check{n}}(k))+{\check{e}}(k)-m, \\ v(n)&=(p-2)(n-{\check{n}}(k))+{\check{v}}(k)-m. \end{aligned}$$

Now, we compute m with the help of the sequence $d_{k,i}$. The vertex $x_{k,1}$ has degree $d_{k,1}$ in $A_{p,q}(k)$; hence, it needs $q-d_{k,i}+1$ tiles to become saturated. Therefore, if $n-{\check{n}}(k) \le q-d_{k,1}$ then $m=0$. Now, for $i>1$, the vertex $x_{k,i}$ has degree $d_{k,i}$ in $A_{p,q}(k)$, but in the spiral, there is already a tile attached to both $x_{k,i-1}$ and $x_{k,i}$; so, $x_{k,i}$ needs $q-d_{k,i}$ tiles to become saturated. Note that the last vertex, $x_{k,{\check{e}}_1(k)}$, will need $q-d_{k,1}-1$ tiles to become saturated due to the presence of the first tile in this layer, so this analysis holds for ${\check{n}}(k)< n < {\check{n}}(k+1)$. Finally, taking into account that $n-{\check{n}}(k)$ must be between the number of tiles needed to saturate m vertices and the number of tiles needed to saturate $m+1$ vertices, gives us the inequality

$$\begin{aligned} 1+ \sum _{i=1}^m (q-d_{k,i}) \le n-{\check{n}}(k) < 1+ \sum _{i=1}^{m+1} (q-d_{k,i}). \end{aligned}$$

$\square$

We now turn our attention to the properties of the dual graph of $S_{p,q}(n)$. We will denote the ith tile of the $\{q,p\}$-spiral, $S_{q,p}(i)$, as $T^{q,p}_i$. Recall that $n'$ is the number of faces in the dual graph, and $e_{2,i}$ is the number of edges that are incident to i faces in the dual graph. We will then show that $S'_{p,q}(n)$ is the $\{q,p\}$-spiral $S_{q,p}\left( n'\right)$, with $e_{2,0}$ many additional edges not included in any of the faces. The additional edges are a path that is formed in the process of closing the next face of the dual, which will be the tile $T^{q,p}_{n'+1}$.

Recall the following facts about how parameters of the dual structure relate back to the original:

• (1) Vertices of the dual graph are in 1-to-1 correspondence with tiles of the original.

• (2) The gluing parameter of a tile in the original animal counts exactly the number of new edges in the dual that connect to the tile’s corresponding vertex.

• (3) Faces of the dual graph are in 1-to-1 correspondence with interior, i.e., saturated, vertices of the original.

Lemma 4.5

The dual graph of $S_{p,q}(n)$ consists of the $\{q,p\}$-spiral animal $S_{q,p}\left( n'\right)$, for $n'=v_{int}\left( S_{p,q}(n)\right)$, with a possibly trivial path of $e_{2,0}$-edges attached. Moreover, if $T^{q,p}_{n'+1}$ is $\epsilon$-glued to $S_{q,p}\left( n'\right)$, then $e_{2,0}(n)\le q-2-\epsilon$.

Proof

Label the vertex of $S'_{p,q}(n)$ corresponding to the tile $T_i$ as $x'_i$, and recall that the definition of a spiral requires that vertices on the perimeter of $A_{p,q}(k)$ are saturated in sequential order. In general, for a tile T in a $\{p,q\}$-animal, its corresponding dual vertex $x'$ is saturated if and only if a copy of $A_{p,q}(2)$ centered at T is filled in, which is equivalent to all of the vertices of T being saturated. We then say that a tile T in a $\{p,q\}$-animal is completely saturated when all of its vertices are saturated.

It is not hard to see that the tiles $T_1, T_2,\ldots$ of the $\{p,q\}$-spiral become completely saturated in sequential order. This is because the perimeter vertices of the kth layer are labeled sequentially from the first tile added in that layer to the last, and a single tile’s vertices on the perimeter of $A_{p,q}(k)$ are consecutive and thus sequentially labeled. Hence, since the perimeter vertices are saturated in sequential order, we have that the tiles of the $\{p,q\}$-spiral become completely saturated in sequential order. Therefore, in the dual $S'_{p,q}(n)$, the vertices $x'_1, x'_2,\ldots ,$ become saturated in sequential order. Now, let the total ordering of the vertices of the $\{p,q\}$-spiral refer to the order induced by lining up each perimeter layer one after another, i.e.,

$$\begin{aligned} x_{1,1}, x_{1,2}, \ldots , x_{1,p}, x_{2,1},\ldots , x_{2,{\check{e}}_1(2)}, x_{3,1},\ldots , x_{3,{\check{e}}_1(3)},x_{4,1},\ldots . \end{aligned}$$

We will then show inductively that the ordering of the $x'_i$ matches that of the total ordering of the $\{q,p\}$-spiral, so that the dual satisfies the conditions of Definition 4.1. To denote the switch from $\{p,q\}$ to $\{q,p\}$ in the dual, we will refer to the vertices of the $\{q,p\}$-spiral by adding a prime to the notation listed above.

With the first tile $T_1=S_{p,q}(1)$, we trivially have that $S'_{p,q}(1)$ is a single isolated vertex. And whenever $T_{n+1}$ is 1-glued to $S_{p,q}(n)$, it adds a vertex of degree 1 to the dual, with a single dual edge corresponding to where $T_{n+1}$ is glued to $T_n$. Thus, the first $q-1$ tiles simply create a path, which is closed with the addition of $T_q$. That is, the tile $T_q$ saturates the vertex $x_{1,1}$ of $T_1$, yielding $S'_{p,q}(q)=S_{q,p}(1)=T^{q,p}_1$. As a convention, we can set the labels of the vertices of this first dual tile $T^{q,p}_1$ to match those required above, e.g., $x'_{1,i}=x'_i$ for $1\le i\le q$.

Now, assume that for some fixed $n\ge q$, the statement of the lemma holds for all $j\le n$, and that $S'_{p,q}(n)=S_{q,p}\left( n'\right)$. Additionally, assume that the ordering of the $x'_i$ matches the total ordering of the vertices of $S_{q,p}\left( n'\right)$.

Let $x_{k,i}$ be the most recently saturated vertex in constructing $S_{p,q}(n)$, so that it is the vertex which corresponds to the tile $T^{q,p}_{n'}$ in the dual (see Fig. 9). Then, let $x_{*}$ be the vertex following $x_{k,i}$ in the total ordering for the $\{p,q\}$-spiral, i.e., the next vertex which will become saturated, and let $T_{*}$ be the tile in the dual tessellation which corresponds to saturating $x_{*}$. We aim to prove that $T_{*}$, which will necessarily be the next tile created in the dual, is in fact $T^{q,p}_{n'+1}$.

By Definition 3.5, $x_{*}$ is adjacent to $x_{k,i}$ in both of the possible cases that $x_{*}=x_{k,i+1}$ or $x_{*}=x_{k+1,1}$. Hence, the dual tiles $T_{*}$ and $T^{q,p}_{n'}$ share an edge, which corresponds to the two tiles in $S_{p,q}(n)$ which contain the edge $\{x_{k,i},x_{*}\}$. Note that $T_n$ must be the tile which completes the saturation of $x_{k,i}$, since any further tiles would either saturate $x_{*}$ or contribute to a path of 1-glued tiles, which contain $e_{2,0}$ edges. But $e_{2,0}=0$ by the assumption that $S'_{p,q}(n)=S_{q,p}\left( n'\right)$. Therefore, $T_n$ is one of the two tiles containing the edge $\{x_{k,i},x_{*}\}$, and we denote the other such tile by $T_{\bullet }$. Let $x'_{\bullet }$ be the vertex of $S'_{p,q}(n)$ corresponding to the tile $T_{\bullet }$. Note that $T_{*}$ contains the vertex $x'_{\bullet }$, since $T_{\bullet }$ contains $x_{*}$. We will show that $T_{\bullet }$ is the next tile to become saturated in the $\{p,q\}$-spiral, and $x'_{\bullet }$ is the next vertex to become saturated in the total ordering of the vertices of the $\{q,p\}$-spiral. This would imply $T_{*}=T^{q,p}_{n'+1}$, since $T_{*}$ contains $x'_{\bullet }$ and it is adjacent to $T^{q,p}_{n'}$.

Fig. 9

The $\{p,q\}$-spiral with vertices $x_{k,i}$, $x_{*}$ and tiles $T_n$ and $T_{\bullet }$ on the left, and the corresponding dual structure on the right

We now consider the two cases, $x_{*}=x_{k+1,1}$ or $x_{*}=x_{k,i+1}$. In the first case, $x_{k,i}=x_{k,{\check{e}}_1(k)}$ and $T_n$ closes the kth layer. Then, $T_{\bullet }$ is the first tile in the kth layer and it is indeed the next tile to become saturated in the spiral construction. In the second case, $T_n$ belongs to the $(k+1)$th layer and $T_{\bullet }$ is in the kth layer. Since tiles in the kth layer and their perimeter vertices are saturated in sequential order, and $T_{\bullet }$ contains $x_{k,i}$, the last vertex to become saturated in $S_{p,q}(n)$, it follows that $T_{\bullet }$ is the next tile to become saturated. Finally, by induction hypothesis, $x'_{1}, \dots , x'_{\bullet }, \dots , x'_n$ agree with the total ordering of the $\{q,p\}$-spiral; thus, $x'_{\bullet }$ is the next vertex to be saturated in the $\{q,p\}$-spiral.

This finishes the proof that $T_{\bullet }$ and $x'_{\bullet }$ are the next tile and vertex to become saturated in their respective spiral. As mentioned before, by construction of the spiral, Definition 4.1, this implies $T_{*} = T^{q,p}_{n'+1}$. Furthermore, tiles are glued to $x_{*}$ in counterclockwise order. Similarly, perimeter vertices of $T_{*}$ are enumerated in counterclockwise order. Then, $T_{n+1}$ corresponds to the next dual vertex along the perimeter of the layer of the $\{q,p\}$-spiral being constructed, or the first vertex of the next layer when $x'_n=x'_{k,{\check{e}}_1(k)}$ for some $k\ge 2$, and so, the labels continue to match the complete ordering of the $\{q,p\}$-spiral.

Finally, we consider the bound on $e_{2,0}$. First, consider the case that $q\ne 3$. From Proposition 3.1 and Remark 3.2, we know that consecutive tiles are 1-glued until a 2-glued tile is added, which saturates a vertex. Consider the process of gluing tiles to $x_{*}$, this corresponds in the dual to adding edges which eventually will form $T^{q,p}_{n'+1}$. Each 1-glued tile in the $\{p,q\}$-spiral contributes one $e_{2,0}$ edge. Meanwhile, the subsequent 2-glued tile adds two edges to the dual, which connect the existing path of $e_{2,0}$ edges to the vertex corresponding to the tile of $S_{p,q}(n)$ which follows $T_{\bullet }$. This 2-glued tile saturates $x_{*}$, creating $T^{q,p}_{n'+1}$ in the dual. And if $T^{q,p}_{n'+1}$ is $\epsilon$-glued, then neither the $\epsilon$ edges which are glued to $S_{q,p}\left( n'\right)$ nor the two edges added by the last 2-glued tile can be counted by $e_{2,0}$. Hence, the bound $e_{2,0}\le q-2-\epsilon$ follows.

If $q=3$, on the other hand, the tile $T_{n+1}$ will either be 2-glued or 3-glued to $S_{p,3}(n)$, saturating either one or two vertices, respectively. A 2-glued tile creates $T^{3,p}_{n'+1}$, while a 3-glued tile also creates $T^{3,p}_{n'+2}$, and in both cases, $e_{2,0}$ is always 0. Note that the dual tiles of $S_{3,p}(n)$ are either 1-glued or 2-glued, since $p\ge 6$. The 1-glued tiles clearly satisfy the bound, as $e_{2,0}=0 \le q-2-\epsilon = 3-2-1 =0$. The 2-glued tiles, on the other hand, are the triangles which share an edge with $A_{3,p}(k)$, for the appropriate k, and have an apex vertex on the perimeter of the next layer. This requires a tile added to $S_{p,3}(n)$ which shares two edges with the perimeter of the previous layer, and thus require that $T_{n+1}$ is 3-glued. However, in this case, $T^{3,p}_{n'+2}$ is 2-glued, but $T^{3,p}_{n'+1}$ is 1-glued, so $T^{3,p}_{n'+1}$ is never 2-glued and the bound holds. $\square$

5 Proof of Theorem 1.8

We now work toward proving Theorem 1.8 and the extremality of the graph properties of $S_{p,q}(n)$. Recall that an animal A with n tiles is said to be extremal if $e_2(A)$ and $v_{int}(A)$ are maximal, and $e(A), e_1(A)$ or v(A) are all minimal in the set of animals with n tiles.

First, we show the maximality of $e_2(n)$ within the class of $\{p,q\}$-graphs with n faces. This requires the following lemma, which asserts that if this holds for the dual structure, then it can be lifted to the original graph.

Lemma 5.1

Let G be a $\{p,q\}$-graph with n faces and $v_{int}$ interior vertices. If $e_{2}\left( G'\right) \le e_2\left( S_{q,p}\left( v_{int}\right) \right)$, then $e_2(G)\le e_2(n)$.

Proof

Recall that $e_{2,2}(G)=e_2\left( G'\right)$. By assumption $e_{2,2}(G)=e_{2}\left( G'\right) \le e_2\left( S_{q,p}\left( v_{int}\right) \right)$. Then, we can plug this into Eq. (2.2)

$$\begin{aligned} e_2(G)&= \frac{q\left( n-c'\right) -e_{2,0}(G) +e_{2,2}(G)}{q-1}, \\&\le \frac{q\left( n-c'\right) + e_{2,2}(G)}{q-1}\\&\le \frac{q\left( n-c'\right) + e_{2}\left( S_{q,p}\left( v_{int}\right) \right) }{q-1}. \end{aligned}$$

To avoid a cacophony of indices and parentheses, we abbreviate our notation when referring to the dual $\{q,p\}$-spiral and write $\tilde{e}_2(i)=e_2\left( S_{q,p}(i)\right)$. Then, applying Euler’s identity for $G'$ to replace $v_{int}$, we have

$$\begin{aligned} e_2(G) \le \frac{q\left( n-c'\right) + \tilde{e}_2\left( v_{int}\right) }{q-1} = \frac{q\left( n-c'\right) + \tilde{e}_2\left( e_2(G)-n+c'\right) }{q-1}. \end{aligned}$$

We can reduce this to the case $c'=1$ using Corollary 4.4 to obtain

$$\begin{aligned} \tilde{e}_2\left( e_2(G)-n+c' \right) =\tilde{e}_2\left( e_2(G)-n+1+c'-1\right) \le \tilde{e}_2\left( e_2(G)-n+1\right) +3\left( c'-1\right) . \end{aligned}$$

And similarly adding and subtracting 1 to $n-c'$ in the first term, we get

$$\begin{aligned} \begin{aligned} e_2(G)&\le \frac{q\left( n-c'\right) + \tilde{e}_2\left( e_2(G)-n+c'\right) }{q-1}, \\&\le \frac{q(n-1) - q\left( c'-1\right) + \tilde{e}_2\left( e_2(G)-n+1\right) + 3\left( c'-1\right) }{q-1}, \\&\le \frac{q(n-1) + \tilde{e}_2\left( e_2(G)-n+1\right) }{q-1}. \end{aligned} \end{aligned}$$

(5.2)

The last inequality follows from the fact that $q\ge 3$, so the coefficient of $\left( c'-1\right)$ is at most 0.

Now, we define the sequence

$$\begin{aligned} g_n(j)=\tilde{e}_2(j-n+1) -(q-1)j +q(n-1), \end{aligned}$$

noting that a simple rearrangement of the inequality in Eq. (5.2) yields $g_n(e_2(G))\ge 0$. To prove $e_2(G)\le e_2(n)$, we will show that $g_n$ is non-increasing, and $j=e_2(n)$ is the last value where it is non-negative.

That $g_n$ is non-increasing is primarily a consequence of Corollary 4.4 applied to the $\{q,p\}$-spiral $S_{q,p}(j-n+1)$. We write $\delta$ for the multiplicative factor in Corollary 4.4, depending here on p instead of q. That is, $\delta = 2$ if $p>3$ and $\delta =3$ if $p=3$. Then, we have

$$\begin{aligned} g_n(j+1)&= \tilde{e}_{2}(j-n+1+1) -(q-1)(j+1) +q(n-1), \\&\le \tilde{e}_{2}(j-n+1)+\delta - (q-1)j -(q-1) + q(n-1), \\&= g_n(j)-q+\delta +1. \end{aligned}$$

Recall that if $p>3$, then $q\ge 3$ and $\delta = 2$. And if $p=3$, then $q\ge 6$ and $\delta =3$. Plugging in q and $\delta$ in either case on the right in this inequality, we get that $g_n(j+1)\le g_n(j)$.

Then, $G= S_{p,q}(n)$ satisfies $e_{2}\left( G'\right) = e_2\left( S_{q,p}\left( v_{int}\right) \right)$ by Lemma 4.5, so by the previous analysis, $g_n(e_2(n))=g_n\left( e_2\left( S_{p,q}(n)\right) \right) \ge 0$. It only remains to show that $g_n\left( e_2(n)+1\right) < 0$. Recall that the dual of $S_{p,q}(n)$ is connected by definition, and is a $\{q,p\}$-spiral with $n'$ faces and possibly some additional edges. Hence, $c'=1$, and by Euler’s formula, the number of faces in the dual is $n'=1-n+e_2(n)$, with $\tilde{e}\left( n'\right) =e_{2}(n)$. Now, we can apply Remark 4.2 to $\tilde{e}_{2}\left( 1-n+e_2(n)+1\right) = \tilde{e}_{2}\left( n'+1\right)$. For $\epsilon$, the gluing parameter of the tile $T_{n'+1}$ in the $\{q,p\}$-spiral, we get that

$$\begin{aligned} g_n\left( e_2(n)+1\right)&= \tilde{e}_{2}\left( n'+1\right) -(q-1)\left( e_2(n)+1\right) +q (n-1), \\&= \tilde{e}_{2}\left( n' \right) +\epsilon -(q-1)e_2(n) -(q-1) +q (n-1). \end{aligned}$$

And Eq. (2.2) for $G=S_{p,q}(n)$ yields that

$$\begin{aligned} e_{2,0}(n)&= e_{2,2}(n)-(q-1)e_2(n)+q(n-1),\\&= \tilde{e}_{2}\left( n' \right) -(q-1)e_2(n) +q (n-1). \end{aligned}$$

Therefore, we have

$$\begin{aligned} g_n\left( e_2(n)+1\right) =e_{2,0}(n)+\epsilon - (q-1). \end{aligned}$$

Finally, Lemma 4.5 tells us that $e_{2,0}(n)\le q-2-\epsilon$, and hence, $g_n\left( e_2(n)+1\right) \le -1$. Therefore, since $g_n\left( e_2(G)\right) \ge 0$, it must be that $e_2(G)\le e_2(n)$. $\square$

We use induction and the bounds from Lemma 2.3 to show that this lifting can always be done, and $e_2(n)$ is in fact always maximal in the class of $\{p,q\}$-graphs.

Lemma 5.3

Fix a pair $\{p,q\}$ and $n\ge 0$. If G is a $\{p,q\}$-graph with n faces, then $e_2(G)\le e_2(n)$.

Proof

Assume that the connected components of G have at least one face; otherwise, they can be ignored, because they do not contribute to $e_2$.

We proceed by induction, leveraging the dual structure and Lemma 4.5 to zipper cases together from the $\{p,q\}$ setting to the $\{q,p\}$ setting, and vice versa. Let $\mathcal {I}(p,q,n)$ be the statement:

$$\begin{aligned} \text {``If }G\text { is a }\{p,q\}\text {-graph with exactly }n\text { faces, then }e_2(G) \le e_2(n)\text {.''} \end{aligned}$$

Our initial base case will be that $\mathcal {I}(p,q,n)$ holds for all p, q and n, such that $n\le q$. When $n < q$, there cannot be any interior vertices. Therefore, the dual graph of G is either a tree, a disjoint union of trees, or the empty graph on n vertices, and $e_2(G)=e\left( G'\right) \le n-1 =e_2(n)$. Similarly, when $n=q$, the optimal value is obtained when the dual graph is a q-cycle, then $e_2(G)\le q =e_2(q)$.

We observe that for any $\{p,q\}$-graph G with n faces and all possible values of $v_{int}(G)$, Lemma 5.1 asserts that $\mathcal {I}(p,q,n)$ follows from knowing that $\mathcal {I}\left( q,p,v_{int}(G)\right)$. To make this observation rigorous, we combine Lemma 5.1 with the bounds in Lemma 2.3 for $v_{int}(G)$ in terms of n to get the following three facts:

• (1) For $p,q\ge 4$, $\mathcal {I}(p,q,n)$ follows from the set $\{\mathcal {I}(q,p,i): i\le n-1\}$.

• (2) For $p=3$, $\mathcal {I}(3,q,n)$ follows from the set $\{\mathcal {I}(q,3,i): i\le \lfloor n/2 \rfloor \}$.

• (3) For $q=3$, $\mathcal {I}(p,3,n)$ follows from the set $\{\mathcal {I}(3,p,i): i\le 2n-2\}$.

First, we focus on using (1) to prove that ${\mathcal {I}}(p,q,n)$ holds with $p,q\ge 4$ for any n. Fix $q\ge 4$. On the one hand, if $n\le q$, then $\mathcal {I}(p,q,n)$ holds by the base case. On the other hand, if $q < n \le p$, we have that $v_{int}(G) < p$ for any $\{p,q\}$-graph G by Lemma 2.3. Hence, $\mathcal {I}\left( q,p,v_{int}(G)\right)$ is satisfied by the base cases, and for any pair $p,q\ge 4$. We conclude that $\mathcal {I}(p,q,n)$ holds for all $n\le \max (p,q)$.

Now, suppose that for all ordered pairs (p, q), such that $p,q\ge 4$, the statement $\mathcal {I}(p,q,i)$ holds for all $i\le \max (p,q)+j$ for some fixed integer $j\ge 0$. Note that for any such fixed pair (p, q), we can switch their roles and we have that $\mathcal {I}(q,p,i)$ also holds for all $i\le \max (p,q)+j$ by this same assumption. Then, for any such fixed pair (p, q), let $n=\max (p,q)+j+1$. The statement $\mathcal {I}(q,p,n-1)$ holds by the inductive assumption, and therefore, $\mathcal {I}(p,q,n)$ follows by statement (1). Applying this to each ordered pair (p, q) with $p,q\ge 4$ allows us to increment j by 1 in the assumption. Therefore, for all $p,q\ge 4$, the statement $\mathcal {I}(p,q,n)$ holds for all n.

Next, we consider the cases where one parameter is fixed at 3, and apply statements (2) and (3) to perform the induction. While one parameter is fixed at 3, we denote the other parameter by $r \ge 6$, and begin by looking at $\mathcal {I}(r,3,n)$. Recall that from the base case argument, the dual statement $\mathcal {I}\left( 3,r,v_{int}(G)\right)$ holds for all $v_{int}(G)\le r$. Combining this with statement (3), we have that $\mathcal {I}(r,3,n)$ holds if $2n-2 \le r$, and hence, for all $n\le (r+2)/2$. Conversely, applying statement (2) to $\mathcal {I}(3,r,n)$ requires that we have $\mathcal {I}\left( r,3,v_{int}(G)\right)$ for all $v_{int}(G)\le \lfloor n/2 \rfloor$. Plugging in $\lfloor n/2 \rfloor$ in place of n in the preceding argument for the $q=3$ case, we get that $\mathcal {I}(r,3,\lfloor n/2 \rfloor )$ holds if $\lfloor n/2 \rfloor \le (r+2)/2$, this is the case whenever $n\le r+2$ regardless of the parity of n. Hence, for every $r\ge 6$, we have that $\mathcal {I}(r,3,n)$ holds for $n\le (r+2)/2$, and $\mathcal {I}(3,r,n)$ holds for $n\le r+2$. We expand our set of base cases to include these two inequalities, and proceed to zipper them together in the induction step.

Fix any $r\ge 6$, and suppose that for a fixed $j\ge 0$, $\mathcal {I}(r,3,i)$ holds for all $i\le \lfloor (r+2)/2\rfloor +j$, and additionally that $\mathcal {I}(3,r,i)$ holds for all $i\le r+2+2j$. Let $n=\lfloor (r+2)/2\rfloor +j+1$, so that by assumption, we know $\mathcal {I}(r,3,i)$ holds for all $i\le n-1$. Note that regardless of the parity of r, $2n-2\le r+2+2j$. Hence, the necessary dual statements $\mathcal {I}(3,r,i)$ all hold by the inductive assumption, and applying statement (3) yields that $\mathcal {I}(r,3,n)$ holds as well.

For the dual $p=3$ case, we need to consider two cases for n, since $r+2+2j$ increments by 2 every time j is increased by 1. Observe that for both $n=r+2+2j+1$ and $n=r+2+2j+2$, we have that $n/2 \le (r+2)/2+j+1$. By the preceding argument in the $q=3$ case, we know that $\mathcal {I}(r,3,i)$ holds for all $i\le (r+2)/2+j+1$. Thus, by applying statement (2), we have that $\mathcal {I}(3,r,n)$ holds for both $n=r+2+2j+1$ and $n=r+2+2j+2$.

Hence, we can increment j by 1 for every $r\ge 6$ in both the $p=3$ case and the $q=3$ case. Therefore, by induction, $\mathcal {I}(r,3,n)$ and $\mathcal {I}(3,r,n)$ hold for all $r\ge 6$ and all $n\ge 0$. $\square$

The maximality of $e_2(n)$ can immediately be churned into the full litany of extremal properties of spiral animals in the class of $\{p,q\}$-graphs. As a corollary, we obtain a proof of the statement of Theorem 1.8 in the particular case for animals with no holes.

Corollary 5.4

Let A be a $\{p,q\}$-animal with n tiles and no holes. Then, $e_2(A)\le e_2(n)$, $v_{int}(A)\le v_{int}(n)$, $e_1(A)\ge e_1(n)$, $e(A)\ge e(n)$, and $v(A)\ge v(n)$.

Proof

Any $\{p,q\}$-animal A with no holes can be regarded as a $\{p,q\}$-graph. Lemma 5.3 implies that $e_2(A)\le e_2(n)$, and the remaining inequalities are obtained from the relations between the graph parameters: $e=e_1+e_2=p\cdot n-e_2$; $e_1=p\cdot n - 2e_2$; $v_{int}=1+e_2-n$; and $v=1-n+e$. $\square$

To prove Theorem 1.8, it remains to show that this corollary also holds for animals with holes. We will use induction on the number of holes to complete the proof, but first we require the following lemma stating that the number of interior edges in $S_{p,q}(n)$ plus the total number of edges in $S_{p,q}(l)$ is at least the number of interior edges in $S_{p,q}(n+l)$.

Lemma 5.5

For any fixed $n > 1$ and fixed $l\ge 1$

$$\begin{aligned} e_2(n)+e(l) \ge e_2(n+l)+1. \end{aligned}$$

Proof

Note that $e(l) = p\cdot l - e_2(l)$. By Corollary 4.4 along with the base case $e_2(1)=0$, we know that $e_2(l) \le \delta \cdot (l-1)$, where $\delta =2$ for $q>3$, and $\delta =3$ for $q=3$. Consider the case $p\ge 4$, and note that $\delta =3$ requires that $q=3$, which forces $p\ge 6$. Hence, for $p\ge 4$, we have $p\ge 2\delta$ for both cases that $\delta =2$ or $\delta =3$, and thus, we get

$$\begin{aligned} e_2(n)+e(l)&= e_2(n)+p\cdot l - e_2(l), \\&\ge e_2(n)+p\cdot l - \delta \cdot (l-1), \\&\ge e_2(n)+\delta \cdot l+\delta , \\ {}&\ge e_2(n+l)+1. \end{aligned}$$

We use that $p\ge 2\delta$ implies $p-\delta \ge \delta$ in the third line, and that $\delta > 1$ in the next line. The last inequality also employs Corollary 4.4 once again.

When $p=3$, we need a sharper analysis. Note that $p=3$ forces $q\ge 6$, and so, all tiles are either 1-glued or 2-glued. Therefore, the increments of the sequence $e_2(l)-l$ are either 0 or 1, respectively. Furthermore, up to a small offset due to the initial value being $e_2(1)-1 = -1$, this sequence counts the number tiles that are 2-glued. Recall that these 2-glued tiles are exactly those that complete the saturation of a perimeter vertex, forcing it to the interior. Since for $p=3$, the perimeter vertices of $A_{p,q}(k)$ have degree $\le 4$, we need at least $q-3$ tiles to surround a perimeter vertex, the first and last of which are always 2-glued. Thus, the increments of 1 are separated by at least $q-5$ increments of 0. On the other hand, for fixed n, the sequence $e_2(n)+2l-e_2(n+l)$ counts the number of 1-glued tiles added when constructing $S_{p,q}(n+l)$ starting from $S_{p,q}(n)$. The increments of this sequence are again 0 or 1, but now the increments by 0 are the 2-glued tiles. Since 1-glued tiles are added at a consistent ratio of at least $q-5$ to 1, and $e_2(l)-l$ actually starts at -1, we conclude that

$$\begin{aligned} e_2(n)+2l-e_2(n+l)&\ge e_2(l)-l+1,\\&= 3l - e(l) - l+1. \end{aligned}$$

The equality here follows from the edge partition formula $e(l)=pl-e_2(l)$ with $p=3$ here, and then, a simple rearrangement of the inequality gives the desired result. $\square$

Proof of Theorem 1.8

Let $h\ge 0$ and suppose that $e_2(n), v_{int}(n)$ are maximal and v(n) is minimal in the class of $\{p,q\}$-animals with n tiles and at most h holes. Let A be a $\{p,q\}$-animal with n tiles and $h+1$ holes. Let H be one of the holes of A, where H itself is regarded as a $\{p,q\}$-animal, and let l be the number of tiles of H. Denote by ${\bar{A}}$ the $\{p,q\}$-animal obtained by filling in H in A. This is an animal with $n+l$ tiles and h holes, so by the induction hypothesis $e_2(n+l) \ge e_2\left( {\bar{A}}\right)$, $v_{int}(n+l) \ge v_{int}\left( {\bar{A}}\right)$, and $v(n+l) \le v\left( {\bar{A}}\right)$. Note that $e(H)\ge e(l)$, since H is a $\{p,q\}$-animal with no holes and that $e_2\left( {\bar{A}}\right) =e_2(A)+e(H)$. Thus, Lemma 5.5 implies that

$$\begin{aligned} e_2(n)+e(l)&\ge e_2(n+l),\\&\ge e_2\left( {\bar{A}}\right) ,\\&= e_2(A)+e(H),\\&\ge e_2(A)+e(l). \end{aligned}$$

Therefore, by induction we conclude that $e_2(n)\ge e_2(A)$ for any $\{p,q\}$-animal A with n tiles.

The inequalities for v and $v_{int}$ are deduced similarly. Using $e=p\cdot n-e_2$, the inequality of Lemma 5.5 can be then written as

$$\begin{aligned} p\cdot n -e(n) + p\cdot l -e_2(l)&\ge p\cdot (n+l) -e(n+l) +1 , \\ e(n+l)&\ge e_2(l)+e(n) +1 . \end{aligned}$$

Now, since H is an animal with no holes, we know $v_{int}(l) \ge v_{int}(H)$. Note that $v\left( {\bar{A}}\right) = v(A)+v_{int}(H)$, then by the induction hypothesis

$$\begin{aligned} v(n+l) \le v\left( {\bar{A}}\right) = v(A)+v_{int}(H) \le v(A)+v_{int}(l) . \end{aligned}$$

We use Euler’s formula on $S_{p,q}(n+l)$, $S_{p,q}(n)$ and the dual of $S_{p,q}(l)$ to get

$$\begin{aligned} v(n+l)&= 1+e(n+l) - (n+l) , \\&\ge 1+e_2(l)+e(n)+1-n-l, \\&= (1+e_2(l)-l) + (1+e(n)-n), \\&= v_{int}(l) + v(n) . \end{aligned}$$

Therefore, $v(A)\ge v(n)$, and this concludes the induction for v. An analogous argument using $v(l) \le v(H)$ and $v_{int}(n+l) \ge v_{int}\left( {\bar{A}}\right) =v_{int}(A)+v(H)$ proves the bound $v_{int}(A)\le v_{int}(n)$ for any $\{p,q\}$-animal A with n tiles.

The inequalities for e and $e_1$ follow, as they did for Corollary 5.4, due to the relations $e=p\cdot n-e_2$, $e_1=p\cdot n-2e_2$, valid for any $\{p,q\}$-animal. $\square$

Corollary 5.6

Let A be a $\{p,q\}$-animal with n tiles and $e_1(A)=e_1(n)$. Then, $e(A)=e(n), e_2(A)=e_2(n), v(A)=v(n), v_{int}(A)=v_{int}(n)$ and A has no holes.

Proof

As before, $e_2(A)=e_2(n)$ and $e(A)=e(n)$ follows from $2e_2=p\cdot n-e_1$ and $e=e_1+e_2$. Let h be the number of holes of A. Euler’s formula for A and $S_{p,q}(n)$ tells us that

$$\begin{aligned} v(A)-e(A)+(n+h) = 1 = v(n)-e(n)+n . \end{aligned}$$

Then, $v(A)+h = v(n)$, but $v(A)\ge v(n)$; these two imply $h=0$ and $v(A)=v(n)$. Finally, since A has no holes, Euler’s formula for the duals of A and $S_{p,q}(n)$, $n-e_2(A)+v_{int}(A)=1=n-e_2(n)+v_{int}(n)$, tells us that $v_{int}(A)=v_{int}(n)$. $\square$

Given the extremality of all the pertinent graph parameters, we now briefly show how to derive the equations from [8] for the Euclidean cases.

Proof of Corollary 1.9

For the case $\{p,q\}=\{3,6\}$, we know ${\check{n}}(k)=6k^2-6k+1$ and, from Example 3.6(A), the sequence $d_k$ is equal to $\underbrace{4,4\dots , 4,3}_{k}\underbrace{4,4\dots , 4,3}_{k-1}$, repeated 3 times, for $k\ge 3$. From these values, we deduce the following formula for $e_1(n)$ valid for $k\ge 3$:

$$\begin{aligned} e_1(n) = {\left\{ \begin{array}{ll} 6k-3 + \bmod (n-1,2) &{} \text {if }0\le n-{\check{n}}(k)\le 1 \\ 6k-2 + \bmod (n,2) &{} \text {if }2\le n-{\check{n}}(k)\le 2k-1 \\ 6k-1 + \bmod (n-1,2) &{} \text {if }2k\le n-{\check{n}}(k)\le 4k-1 \\ 6k + \bmod (n,2) &{} \text {if }4k\le n-{\check{n}}(k)\le 6k \\ 6k+1 + \bmod (n-1,2) &{} \text {if }6k+1\le n-{\check{n}}(k)\le 8k-1 \\ 6k+2 + \bmod (n,2) &{} \text {if }8k\le n-{\check{n}}(k)\le 10k \\ 6k+3 + \bmod (n-1,2) &{} \text {if }10k+1\le n-{\check{n}}(k)\le 12k-1. \\ \end{array}\right. } \end{aligned}$$

Then, it is a straightforward computation to check that it can be written as

$$\begin{aligned} e_1(n)&= 2 \left\lceil \frac{1}{2}( n+\sqrt{6n}) \right\rceil - n. \end{aligned}$$

A similar analysis holds for the cases $\{p,q\}=\{4,4\}$ and $\{6,3\}$. $\square$

6 Enumeration of Extremal $\{p,q\}$-Animals

In [17], Kurz enumerated polyominoes, i.e., $\{4,4\}$-animals, that attain minimum perimeter for any fixed number of tiles. Moreover, he proved that for all $l\ge 1$, there exists a unique polyomino with $l^2$ tiles which is extremal, and also a unique extremal polyomino with $l(l+1)$ tiles. The former are the square shape polyominoes with side lengths l, and the latter are pronic rectangles with side lengths l and $l+1$. In the general $\{p,q\}$ setting, we find that the sequence $A_{p,q}(k)$ corresponds precisely to squares with odd side lengths, and we define three more sequences corresponding to even squares and the two types of pronic rectangles distinguished by the parity of the shorter side. We are then able to generalize Kurz’s result and show that each of these sequences yields unique extremal $\{p,q\}$-animals for any p and q.

First, we define the sequence $B_{p,q}(k)$ analogously to $A_{p,q}(k)$; but start with $B_{p,q}(1)=x_0$, a single vertex. Then, $B_{p,q}(2)$ is the set of q tiles incident to $x_0$, and $B_{p,q}(3)$ is the set of all tiles incident to the perimeter of $B_{p,q}(2)$, and so on. These form another distinct subsequence of spirals that are related to the $A_{p,q}(k)$ through the dual graph. Observe that the $B_{p,q}(k)$ sequence corresponds directly to the square-shaped polyominoes with even side length in the $\{4,4\}$ case.

Remark 6.1

From Lemma 4.5, we know that the dual of $A_{p,q}(k)$ is $B_{q,p}(k)$, and thus, $B_{p,q}(k)=S_{p,q}(n)$ for $n=v_{int}\left( A_{q,p}(k)\right)$. Similarly, the dual of $B_{p,q}(k)$ is $A_{q,p}(k-1)$.

We will use the duality of these two structures to build an inductive proof of their uniqueness, but first, we require a short proposition establishing a condition under which, up to isometries, an animal and its dual graph are in 1-to-1 correspondence.

Proposition 6.2

Let A be a $\{p,q\}$-animal, such that $e_{2,0}(A)=0$. If M is a $\{p,q\}$-animal with $M'=A'$, then $M=A$.

Proof

The faces of $A'$ always represent a set of vertices in the $\{p,q\}$-lattice which are saturated in A. By definition, a vertex is saturated if and only if all q incident tiles are present in A. However, if $e_{2,0}(A)=0$, then every vertex of $A'$ is incident to a face of $A'$, and hence, every tile of A is incident to a saturated vertex of A. Therefore, a tile is in A if and only if it is incident to a saturated vertex. But then, $M'=A'$ implies that also $e_{2,0}(M)=0$, so by the same reasoning, a tile is in M if and only if it is incident to a saturated vertex. Therefore, since A and M have the same set of saturated vertices, it must be that $M=A$. $\square$

Theorem 6.3

For any $k\ge 1$, $A_{p,q}(k)$ is the unique extremal $\{p,q\}$-animal with ${\check{n}}(k)$ tiles. Similarly, for $k\ge 2$, $B_{p,q}(k)$ is the unique extremal $\{p,q\}$-animal with $v_{int}\left( A_{q,p}(k)\right)$ tiles.

Proof of Theorem 6.3

The statement is trivially true for $A_{p,q}(1)$ for all p and q. The induction will proceed by zippering the two sequences, with $B_{p,q}(k)$ following from $A_{q,p}(k-1)$ and then $A_{p,q}(k)$ following from $B_{q,p}(k)$.

Suppose that $A_{p,q}(k-1)$ is a unique extremal animal for all p and q. Then, for any fixed p and q, let B be a $\{p,q\}$-animal with $n(B)=n\left( B_{p,q}(k)\right)$ and perimeter $e_1(B)=e_1\left( B_{p,q}(k)\right)$. By Corollary 5.6, we then have that B has no holes and it has the same number of interior edges and interior vertices as $B_{p,q}(k)$. Thus, $B'$ has the same number of edges and faces as the dual of $B_{p,q}(k)$, which is $A_{q,p}(k-1)$.

Since $A_{q,p}(k-1)$ is itself a spiral, its number of edges $e_{2,2}\left( B_{p,q}(k)\right)$ is maximal for its number of faces. Hence, $e_{2,2}(B)\le e_{2,2}\left( B_{p,q}(k)\right)$. Then, by Eq. (2.2) with $c'=1$ in both cases, it must be that $e_{2,0}(B)=0$, and thus, $e_{2,2}(A) = e_{2,2}\left( B_{p,q}(k)\right)$. Therefore, the dual of B has the same number of faces, and interior edges as $A_{q,p}(k-1)$. And by our inductive assumption, $A_{q,p}(k-1)$ is the unique animal with these parameters, and it must be that $B'=A_{q,p}(k-1)$. Hence, since $e_{2,0}=0$, by Proposition 6.2, we can lift this equality to get $B=B_{p,q}(k)$, which is therefore the unique extremal animal with $v_{int}\left( A_{q,p}(k)\right)$ tiles.

The exact same argument suffices to show that the uniqueness of $A_{p,q}(k)$ follows from knowing uniqueness for $B_{q,p}(k)$. Therefore, by induction, we have uniqueness of $A_{p,q}(k)$ for all $k\ge 1$, and for $B_{p,q}(k)$ for all $k\ge 2$. $\square$

To extend now the pronic case, we define two more sequences in a similar fashion to the $A_{p,q}(k)$ and $B_{p,q}(k)$. Let $C_{p,q}(1)$ be the $\{p,q\}$-animal which has two tiles glued along a single adjoining edge, and let $D_{p,q}(1)$ be the $\{p,q\}$-graph which is simply a single edge connecting two vertices. Then, the sequences $C_{p,q}(k)$ and $D_{p,q}(k)$ are defined analogously, with all possible tiles incident to the perimeter added in each subsequent step (Fig. 10).

Fig. 10

Left: $B_{4,5}(3)$ and its dual $A_{5,4}(2)$. Center: $C_{3,7}(2)$ and its dual $D_{7,3}(2)$. Right: $C_{7,3}(2)$ and its dual $D_{3,7}(2)$

Theorem 6.4

For any $k\ge 1$, $C_{p,q}(k)$ is a unique extremal animal. Similarly, for any $k\ge 2$, $D_{p,q}(k)$ is a unique extremal animal.

Proof

The dual of $C_{p,q}(k)$ is $D_{q,p}(k)$, and the dual of $D_{p,q}(k)$ is $C_{q,p}(k-1)$. It is clear that up to isometries there is only one $\{p,q\}$-animal on two tiles, and hence, $C_{p,q}(1)=S_{p,q}(2)$ is unique. Note that $e_{2,0}\left( C_{p,q}(k)\right) = e_{2,0}\left( D_{p,q}(k)\right) =0$ for $k\ge 2$. Then, an inductive argument using Proposition 6.2 shows that $C_{p,q}(k)$ and $D_{p,q}(k)$ are subsequences of the spiral $S_{p,q}(n)$, and hence are extremal. The proof of their uniqueness then follows by the same inductive argument as in the proof of Theorem 6.3. $\square$

Remark 6.5

The formulas for the number of tiles and vertices of $C_{p,q}(k)$ can be obtained using the same method as in Theorem 1.3, and are as follows:

$$\begin{aligned}&n\left( C_{p,q}(k)\right) \\&\quad = \frac{2}{(\alpha -1)\sqrt{t^2-4}} \left( \alpha ^{k+1} + \alpha ^{-k}-\alpha -1 + (q-1)\left( \alpha ^{k} + \alpha ^{-(k-1)}-\alpha -1 \right) \right) , \\&v\left( C_{p,q}(k)\right) \\&\quad = \frac{2}{(\alpha -1)\sqrt{t^2-4}} \left( (p-1)\left( \alpha ^{k+1} + \alpha ^{-k}-\alpha -1 \right) + \alpha ^{k} + \alpha ^{-(k-1)}-\alpha -1 \right) . \end{aligned}$$

Finally, to obtain the parameters for $D_{p,q}(k)$, we just need to use the duality between the two families. Indeed, $n\left( D_{p,q}(k)\right) = v\left( C_{q,p}(k-1)\right)$, and $v\left( D_{p,q}(k)\right) = n\left( C_{q,p}(k)\right)$.

Fig. 11

Extremal $\{4,5\}$-animals with 9 tiles

As shown in Fig. 11, it is not always the case that all $\{p,q\}$-spirals are unique extremal animals. In the $\{4,5\}$-tessellation, for example, it is straightforward to construct an animal with 9 tiles which is extremal, but not equivalent to $S_{4,5}(9)$, up to isometries. Note that $A_{4,5}(2)$ has 13 tiles, and tiles which are incident to only a vertex of $A_{4,5}(1)$ naturally appear in pairs in the corners. Then, let A be an animal obtained by removing two of these corner pairs. It is simple to compute that both A and $S_{4,5}(9)$ will have $e_1=16$, and since they also have the same number of tiles, all other graph parameters will also be equal. Hence, A is also extremal. Depicted in Fig. 11, we see that there are exactly five distinct extremal $\{4,5\}$-animals with 9 tiles up to isometries, where the image on the far left is $S_{4,5}(9)$. This can be checked by considering all animals with exactly 2 interior vertices, as in $S_{4,5}(9)$, and noting that these two vertices must share an incident tile, as there otherwise must be at least 10 tiles.

7 Conclusions and Open Problems

Recall that Theorem 1.8 asserts that ${\mathcal {P}}_{p,q}(n)$, the minimum perimeter that an n-tile $\{p,q\}$-animal can attain, is equal to $e_1(n)$. Although here we give an algorithm to iteratively find the values of ${\mathcal {P}}_{p,q}(n)$, it remains an open problem to find closed formulas for ${\mathcal {P}}_{p,q}(n)$ in the hyperbolic cases.² The substitution rules seen in Sect. 3 hint at the theory of Sturmian words as a promising approach to finding such formulas. Nevertheless, we can derive some interesting properties of ${\mathcal {P}}_{p,q}$ as a direct consequence of Corollary 4.4 and Theorem 1.8. For instance, we have that ${\mathcal {P}}_{3,q}(n+1)-{\mathcal {P}}_{3,q}(n) = \pm 1$ for $q\ge 6$, ${\mathcal {P}}_{p,q}(n)$ is non-decreasing when $p=4$ or $\{p,q\}=\{6,3\}$, and ${\mathcal {P}}_{p,q}(n)$ is strictly increasing otherwise. These properties are summarized in the following corollary:

Corollary 7.1

For any $\{p,q\}$ with $(p-2)(q-2)\ge 4$,

$$\begin{aligned}&{\mathcal {P}}_{p,q}(n+1)-{\mathcal {P}}_{p,q}(n) = p-2 \text { or }p-4\text {, when }q>3\text {.} \\&{\mathcal {P}}_{p,3}(n+1)-{\mathcal {P}}_{p,3}(n)= p-4 \text { or }p-6\text {, for }n>1\text {.} \end{aligned}$$

In the hyperbolic case, the minimum perimeter is of the order of the number of tiles. Bounds for ${\mathcal {P}}_{p,q}(n)$ for sufficiently large n can be obtained from the following corollary to Theorem 1.6 bounding $e_2(n)$.

Corollary 7.2

Assume $(p-2)(q-2)>4$. For $p\ge 4$ and $n>{\check{n}}(3)$, we have

$$\begin{aligned} n+\frac{n-1}{q-2}< e_2(n) < n+ \frac{n-1}{q-3}. \end{aligned}$$

For $p=3$ and $n>{\check{n}}(4)$, we have

$$\begin{aligned} n+\frac{n-1}{q-3}< e_2(n) < n+ \frac{n-1}{q-4}. \end{aligned}$$

Proof

We will prove that

$$\begin{aligned} {\check{n}}(k)+\dfrac{{\check{n}}(k)}{q-2} +1< {\check{e}}_2(k)< {\check{n}}(k)+\dfrac{{\check{n}}(k)}{q-3} , \text { if } p\ge 4 \text { and } k\ge 3, \\ {\check{n}}(k)+\dfrac{{\check{n}}(k)}{q-3} +1< {\check{e}}_2(k) < {\check{n}}(k)+\dfrac{{\check{n}}(k)}{q-4} , \text { if } p=3 \text { and } k\ge 4. \end{aligned}$$

We will use the parameter $i=0,1,2$, to encompass the different cases. Recall that $p\cdot n =e_1+2e_2$, then

$$\begin{aligned} 2{\check{e}}_2(k) - 2{\check{n}}(k)\left( 1 + \frac{1}{q-2-i} \right) = {\check{n}}(k)\left( p-2 - \frac{2}{q-2-i} \right) - {\check{e}}_1(k) . \end{aligned}$$

Let $l=p-2 - \frac{2}{q-2-i}$ for $i=0,1,2$. Using formulae (3.4) for ${\check{n}}(k)$ and ${\check{e}}_1(k)$, we get

$$\begin{aligned}&l{\check{n}}(k) - {\check{e}}_1(k) \\&\quad = \frac{p \alpha ^k}{\sqrt{t^2-4}} \left( \frac{l(q-2)}{\alpha -1} - (1+\alpha ^{-1})\right) + \frac{p \alpha ^{-(k-1)}}{\sqrt{t^2-4}} \left( \frac{l(q-2)}{\alpha -1} + (1+\alpha ^{-1})\right) \\&\qquad +l -\frac{l p(q-2)}{(\alpha -1)\sqrt{t^2-4}}(\alpha +1) , \\&\quad = \frac{p \alpha ^k}{(\alpha -1)\sqrt{t^2-4}} \left( l(q-2) - \sqrt{t^2-4} \right) + \frac{p \alpha ^{-(k-1)}}{(\alpha -1)\sqrt{t^2-4}} \left( l (q-2) + \sqrt{t^2-4} \right) \\&\qquad + l -\frac{l p(q-2)}{t-2}, \end{aligned}$$

where, in the last line, we used $(\alpha -1)\left( 1+\alpha ^{-1} \right) =\alpha -\alpha ^{-1}=\sqrt{t^2-4}$ and $\frac{(\alpha +1)}{(\alpha -1)\sqrt{t^2-4}}=\frac{1}{t-2}$. Now, we focus on the term containing $\alpha ^k$

$$\begin{aligned}&\frac{p \alpha ^k}{(\alpha -1)\sqrt{t^2-4}} \left( l(q-2) - \sqrt{t^2-4} \right) \\&\quad = \frac{p \alpha ^k}{(\alpha -1)\sqrt{t^2-4}} \left( (p-2)(q-2) - \frac{2(q-2)}{q-2-i} - \sqrt{t^2-4} \right) , \\&\quad = \frac{p \alpha ^k}{(\alpha -1)\sqrt{t^2-4}} \left( 2 \alpha ^{-1} + 2 - \frac{2(q-2)}{q-2-i} \right) , \\&\quad = \frac{2 p \alpha ^{k-1}}{(\alpha -1)\sqrt{t^2-4}} \left( 1 - \frac{i\alpha }{q-2-i} \right) . \end{aligned}$$

Note that $\frac{2 p \alpha ^{k-1}}{(\alpha -1)\sqrt{t^2-4}} >2p$ for $k\ge 3$. For $i=0$, we get $l{\check{n}}(k) - {\check{e}}_1(k) \ge 2p+l-\frac{l p(q-2)}{t-2} = 2p+p-2-\frac{2}{q-2}-p\frac{(p-2)(q-2)-2}{(p-2)(q-2)-4}$, and this is readily seen to be greater than 2. This implies that ${\check{n}}(k)+\dfrac{{\check{n}}(k)}{q-2} +1 < {\check{e}}_2(k)$. For $i=1$ and $p\ge 4$, using $\alpha +\alpha ^{-1}=(p-2)(q-2)-2$, it can be checked that $1-\frac{\alpha }{q-3}<-\frac{1}{2}$. Then, the the $\alpha ^{k}$-term in $l{\check{n}}(k) - {\check{e}}_1(k)$ is smaller than $-p$. Also, the $\alpha ^{-k}$-term is smaller than 1, and $l<p-2$, so $l{\check{n}}(k) - {\check{e}}_1(k)<0$. This implies ${\check{e}}_2(k)< {\check{n}}(k)+\dfrac{{\check{n}}(k)}{q-3}$ for $k\ge 3$ and $p\ge 4$. For $i=1$, $p=3$ and $k\ge 4$, we have

$$\begin{aligned} l{\check{n}}(k) - {\check{e}}_1(k) > \frac{6\alpha ^3}{(\alpha -1)(\alpha -\alpha ^{-1})}\cdot \left( 1-\frac{\alpha }{q-3} \right) +l-\frac{3l(q-2)}{t-2}. \end{aligned}$$

(7.3)

For $t=q-4$, $\alpha =(t+\sqrt{t^2-4})/2$ and $l=\frac{q-5}{q-3}$, it can be check that, as a function of q, the right-hand side of Inequality (7.3) is greater than 2 for $q\ge 7$. This implies $l{\check{n}}(k) - {\check{e}}_1(k)>2$, so ${\check{n}}(k)+\dfrac{{\check{n}}(k)}{q-3} +1 < {\check{e}}_2(k)$ for $k\ge 4$ and $p=3$. Similarly, for $i=2$ and $p=3$, we have $1 - \frac{2\alpha }{q-4} = 1- \frac{2(q-4-\alpha ^{-1})}{q-4} = -1+\frac{2\alpha ^{-1}}{q-4} < 0$, so

$$\begin{aligned} l{\check{n}}(k) - {\check{e}}_1(k) < \frac{6\alpha ^3}{(\alpha -1)(\alpha -\alpha ^{-1})}\cdot \left( 1-\frac{2\alpha }{q-4} \right) +1 +l-\frac{3l(q-2)}{t-2}. \end{aligned}$$

(7.4)

As a function of q, the right-hand side of Inequality (7.4) is negative for $q\ge 7$. Which implies that $l{\check{n}}(k) - {\check{e}}_1(k)<0$. Therefore, ${\check{e}}_2(k) < {\check{n}}(k)+\dfrac{{\check{n}}(k)}{q-4}$ for $k\ge 4$ and $p=3$.

Finally, given n, choose k, such that ${\check{n}}(k)< n < {\check{n}}(k+1)$. In the case $p\ge 4$, each $d_{k,i}$ is either 2 or 3 so, Formula (1.7) gives the following bound:

$$\begin{aligned} m(q-3)&\le \sum _{i=1}^m (q-d_{k,i}) \le n-{\check{n}}(k)-1 < \sum _{i=1}^{m+1} (q-d_{k,i}) \le (m+1)(q-2), \\ \Longrightarrow &\frac{n-{\check{n}}(k)-1}{q-2}-1 \le m \le \frac{n-{\check{n}}(k)-1}{q-3}. \end{aligned}$$

Then, the bounds for ${\check{e}}_2(k)$ and m together with the formula $e_2(n)=n -{\check{n}}(k)+{\check{e}}_2(k)+m$ give the result. The conclusion for the case $p=3$ is analogous, but now each $d_{k,i}$ is either 3 or 4. $\square$

We further conjecture a sharp limit for this ratio, based on the ratio for the $A_{p,q}(k)$ sequence

Conjecture 7.5

$$\begin{aligned} \lim _{n\rightarrow \infty } \frac{e_2(n)}{n} = \lim _{k\rightarrow \infty } \frac{{\check{e}}_2(k)}{{\check{n}}(k)} = \frac{q-1}{q-2} + \frac{1}{\alpha (q-2)}. \end{aligned}$$

Recall that $e_2(n)$ increments by the gluing parameter of each tile. Therefore, when $q=3$, all tiles are either 2-glued or 3-glued, and thus

$$\begin{aligned} \dfrac{e_2(n)}{n}=\dfrac{2n+(\# \text { of 3-glued tiles})}{n} = 2+\dfrac{\# \text { of 3-glued tiles}}{n}. \end{aligned}$$

And similarly, when $q\ge 4$ all tiles are either 1-glued or 2-glued, and the ratio is

$$\begin{aligned} \frac{e_2(n)}{n}=1+\dfrac{\# \text { of 2-glued tiles}}{n}. \end{aligned}$$

Therefore, this limit is capturing the ratio of these maximally glued tiles in each case. If this limit holds, then all such ratios for the graph parameters of $S_{p,q}(n)$ will also have limits given by the corresponding subsequences for $A_{p,q}(k)$.

One application of finding exact formulas for ${\mathcal {P}}_{p,q}(n)$ is to explore extremal topological animals. Euclidean animals with minimum perimeter have provided the right shape to produce animals with maximally many holes. We expect that the same will hold true for hyperbolic animals. Represent the maximum number of holes that a $\{p,q\}$-animal with n tiles can have by $f_{p,q}(n)$. Then, using techniques introduced in [20], the following topological isoperimetric inequality holds:

$$\begin{aligned} f_{p,q}(n)\le \frac{ n p - 2(n-1) -{\mathcal {P}}_{p,q}(n + f_{p,q}(n))}{p}. \end{aligned}$$

(7.6)

This also provides a measure of certain geometric efficiencies, which are optimized when $f_{p,q}(n)$ attains this upper bound. In the Euclidean case, much of the analysis in solving the question of how many holes an n-tile animal can have stemmed from understanding these efficiencies, and analyzing the gap between $f_{p,q}(n)$ and this bound [20,21,22].

Finally, it is also natural to ask about algebraic characterizations of combinatorial parameters of higher dimensional extremal animals. For example, one can consider face-minimization properties of structures that are built by gluing together d-dimensional polytopes along codimension-1 faces in ${\mathbb {R}}^d$ or ${\mathbb {H}}^d$. In these settings, the analogs of the complete layered animals are straightforward to construct, but it is not immediately clear, for instance, how to generalize the 2-dimensional spirals that interpolate between them.