Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 2 (2009) 173–180
Counting edge-transitive, one-ended,
three-connected planar maps with a given
growth rate
Tomaž Pisanski
Faculty of Mathematics and Physics, University of Ljubljana
Jadranska 19, 1000 Ljubljana, Slovenia
Received 17 January 2008, accepted 4 September 2009, published online 30 September 2009
Abstract
B. Grünbaum and G. C. Shephard have classified one-ended, 3-connected, planar, edge-
transitive maps. It turns out that each of these maps can be described uniquely by an edge-
symbol 〈p, q; k, `〉. Recently the growth rate of each of these maps has been determined
by S. Graves, T. Pisanski and M. E. Watkins. We determine the number of edge-transitive
maps for a given growth rate.
Keywords: Tessellation, edge-transitive, Bilinski diagram, exponential growth, enumeration.
Math. Subj. Class.: 05B45, 05C12, 52C20
Dedicated to Professor Ivan Vidav on the occasion of his 90th birthday.
1 Introduction
All maps in this article are planar, 3-connected, dually 3-connected and one-ended, i.e., the
deletion of no finite subgraph leaves two or more infinite components. Our maps may be
finite or infinite, but are locally finite, i.e., all valences and co-valences are finite. It is well
known that for every such map, there exists a unique planar embedding.
We are interested in the “rate of growth” of such maps. Our measure of this rate of
growth is the limit of the ratio Γ(n) := τ(n + 1)/τ(n) as n approaches infinity, when
such a limit exists, where τ(n) is the number of vertices in the first n layers (also called
coronas) of the Bilinski diagram. We follow [5] and call these maps (edge-transitive planar)
tessellations.
In this article we are interested in obtaining explicit values for the number of edge-
transitive tessellations with a given growth rate. In this case the underlying graph is edge-
homogeneous, i.e., there exists a 4-tuple 〈p, q; k, `〉 of integers ≥ 3, called the edge-symbol
E-mail address: Tomaz.Pisanski@fmf.uni-lj.si (Tomaž Pisanski)
Copyright c© 2009 DMFA Slovenije
174 Ars Math. Contemp. 2 (2009) 173–180
of the tessellation, such that for each edge, p and q are the valences of its two incident
vertices and k and ` are the covalences of its two incident faces.
It is shown in [9] that in case of edge-transitive planar tessellations the growth rate is
independent of the root of the Bilinski diagram. Hence we may define the limit Γ(M) =
limn→∞ Γ(n) without specifying which Bilinski diagram is used for computing Γ(n). Re-
call that a tessellation M is normal if each face is homeomorphic to a closed disk, any two
faces are either disjoint or meet at a vertex or at an edge and there exist two radii r and
R, r < R, such that each face contains a ball of radius r and is entirely contained in a ball
of radius R. Let us define
µ(M) :=
1
p
+
1
q
+
1
k
+
1
`
.
Assume that the tessellation M with the edge symbol 〈p, q; k, `〉 exists. It is well-known
that if µ(M) > 1, then the tessellation M is finite and has a normal realization on the
sphere. More interesting is that when µ(M) = 1, then the tessellation has a normal realiza-
tion in the Euclidean plane E2, τ(n) grows quadratically, and Γ(M) = 1. However, when
µ(M) < 1, then the tessellation has a normal realization in the hyperbolic plane H2, τ(n)
grows exponentially, and Γ(M) > 1.
One would expect that the tessellations with higher growth rate would have smaller
value of parameter µ. This is true for most cases. However, there are numerous counter-
examples. For instance, Γ(〈3, 8; 4, 4〉) > Γ(〈4, 5; 4, 4〉) while µ(〈3, 8; 4, 4〉) > µ(〈4, 5;
4, 4〉); see [5], Table 1. It seems that there is no mapping F that would allow us to compute
Γ if µ is known: Γ(〈p, q; k, `〉) = F (µ(〈p, q; k, `〉)). We could not find any mapping F ′
that would express µ in terms of Γ: µ(〈p, q; k, `〉) = F ′(Γ(〈p, q; k, `〉)). This means that
the connection between the growth rate Γ(M) and parameter µ(M) is much more involved
and is only partially explained in [5].
2 Preliminaries
For the tessellations considered in this article, Grünbaum and Shephard [7] have obtained
the following strong result rewritten according to our needs.
Proposition 2.1. [7] There exists an edge-transitive tessellation with valences p and q and
covalences k and ` if and only if p, q, k, ` are integers such that 3 ≤ p ≤ q and 3 ≤ k ≤ `
and exactly one of the following holds:
(1) all of p, q, k, ` are even;
(2.1) k = ` even, and exactly one of p, q is odd;
(2.2) k = ` even, and both p, q are odd;
(3.1) p = q even, and exactly one of k, ` is odd;
(3.2) p = q even, and both k, ` are odd;
(4) p = q, k = `, and all are odd.
The parameters p, q, k, ` determine the tessellation up to homeomorphism of the plane.
Note that in the original formulation of the theorem, the cases (2.1) and (2.2) are com-
bined into
(2) k = ` even, and at least one of p, q is odd;
and similarly the cases (3.1) and (3.2) into
(3) p = q even, and at least one of k, ` is odd.
If the parameters p, q, k, and ` satisfy the conditions of Proposition 2.1 we call the
corresponding edge symbol 〈p, q; k, `〉 admissible. The result of Grünbaum and Shephard
T. Pisanski: Counting edge-transitive, one-ended, three-connected planar maps. . . 175
shows in the one-ended case not only that each edge-homogeneous tessellation is also edge-
transitive but also that edge-transitive tessellations are in one-to-one correspondence with
admissible edge-symbols. We remark that for a given edge-symbol, there may exist more
than one multi-ended map, but there also may exist none at all, as shown in [4].
In [5] the growth rate of edge-transitive tessellations is computed.
Definition 2.2. Let M be a tessellation that is rooted at some vertex v. Define a sequence
of sets {Un : n ≥ 0} of vertices and a sequence of sets {Fn, : n ≥ 1} of faces as follows:
• Let U0 = {v} and let F0 = ∅;
• For n ≥ 1, let Fn denote the set of faces of M not in Fn−1 that are incident with some
vertex in Un−1;
• For n ≥ 1, let Un denote the set of vertices of M not in Un−1 that are incident with
some face in Fn.
The stratification {Un} and {Fn} is called the Bilinski diagram Bv of M rooted at v.
In a similar way one could define the Bilinski diagram Bf of M rooted at f ; see [5].
These diagrams were first used by Stanko Bilinski in his dissertation [1, 2] and later
also by others such as Grünbaum and Shephard [8]. In [10] they were formally introduced
as “Bilinski maps”.
Intuitively, most tessellations can be labeled as Bilinski diagrams by arbitrarily select-
ing a vertex to comprise the singleton set U0 and then calling by Un each set of vertices
on subsequent concentric circles with (increasing) radius n. The annulus between two con-
secutive concentric circles 〈Un−1〉 and 〈Un〉 is partitioned by the set of faces Fn. Thus the
neighborhood of a vertex in Un is contained in Un−1 ∪ Un ∪ Un+1.
A Bilinski diagram is concentric if each subgraph induced by Un (n ≥ 1) is a circuit.
If a tessellation yields a concentric Bilinski diagram regardless of which vertex or face is
chosen as its root, then the tessellation is uniformly concentric.
For edge-transitive tessellations it is possible to verify that a tessellation either is uni-
formly concentric or is not concentric for any given root. Furthermore, the tessellation is
concentric if and only if its dual is concentric.
Now we can give a precise definition of the function τ(n) defined in the previous sec-
tion. Let the tessellation M be labeled as a Bilinski diagram. Then
τ(n) :=
n∑
j=0
|Un|, n = 0, 1, . . . ,
and the growth rate of M is defined as
Γ(M) = lim
n→∞
τ(n+ 1)
τ(n)
if this limit exists.
In [5] S. Graves, T. Pisanski and M. E. Watkins determined the growth rate Γ(M) of
any tessellation with the admissible edge-symbol 〈p, q; k, `〉. It turns out that the growth
rate can be expressed in terms of a single parameter
t := ((p+ q)/2− 2)((k + `)/2− 2).
Let us define the function
G(t) = (t− 2 +
√
t(t− 4))/2.
176 Ars Math. Contemp. 2 (2009) 173–180
Proposition 2.3. ([3]) Let M be an edge-transitive tessellation with the admissible edge-
symbol 〈p, q; k, `〉, 3 ≤ p ≤ q and 3 ≤ k ≤ `. Then
(a) if p = 3, q ≥ 6, k = ` = 4, then neither M nor its dual are concentric;
(b) in all other cases both M and its dual are uniformly concentric.
Proposition 2.4. ([5]) Let M be an edge-transitive tessellation with the admissible edge-
symbol 〈p, q; k, `〉 or 〈k, `; p, q〉, 3 ≤ p ≤ q and 3 ≤ k ≤ `. Then
Γ(M) = Γ(t) =
{
G(t-1) if the tessellation M is not concentric,
G(t) if the tessellation M is concentric.
There are nine finite tessellations not covered by this Proposition. There are also five
Euclidean tessellations with growth rate 1. All other growth rates are exponential and are
given by the set {G(t)|t = 5, 6, . . . } and are irrational numbers.
3 Counting tessellations with a given growth rate
In this section we will count the number of edge-transitive tessellations with a given growth
rate. Let a0 := 9 denote the number of finite tessellations, a1 the number of Euclidean
tessellations (growth rate Γ1 := 1), a2 the number of tessellations with the smallest expo-
nential growth rate
Γ2 := G(5) = (3 +
√
5)/2
and in general, for any n ≥ 2 let an count the number of tessellations with the growth rate
Γn = G(n+ 3).
Before we state the main result let us recall some divisor functions. Let σk(n) denote
the sum of k-th powers of divisors of a positive integer n: σk(n) =
∑
d|n d
k. Similarly, let
σok(n) denote the sum of k-th powers of odd divisors of the integer n.
Let N(t) denote the number of tessellations with parameter t = ((p+ q)/2− 2)((k +
`)/2−2) for which the edge-symbol 〈p, q; k, `〉 is admissible. First we establish the number
of tessellations N(t) for t ≥ 4.
Theorem 3.1. The number of tessellations with parameter t is given by:
(a) N(t) = t4σ0(
t
4 ) +
t
2 (σ
o
0(t)− σo−1(t)) + 2σo1(t) + 2σ1( t4 ), if t is divisible by 4.
(b) N(t) = t2 (σ0(
t
2 )− σ−1(
t
2 )) + 2σ1(
t
2 ), if t is even but
t
2 is odd.
(c) N(t) = t+14 σ0(t) +
1
2σ1(t), if t is odd.
Proof. In order to prove the result we have to count the number of non-isomorphic admis-
sible edge-symbols 〈p, q; k, `〉 with a given parameter t. Let us write a = (p + q)/2 − 2
and b = (k + `)/2 − 2. Clearly a and b may be half-integers. However, if one is a
half-integer, then the other one must be an even integer, making their product t = ab
an integer. We count separately each of the cases of Proposition 2.1: N(t) = N1(t) +
N2(t) + N3(t) + N4(t) and N2(t) = N21(t) + N22(t), N3(t) = N31(t) + N32(t). Note
that the subscripts of N introduced here are in one-to-one correspondence with each case
or subcase of Proposition 2.1. For instance, N22(t) counts the number of tessellations with
t = ((p+ q)/2− 2)((k + `)/2− 2) such that 3 ≤ p ≤ q, 3 ≤ k ≤ ` where k = ` is even,
and both p, q are odd.
Case 1. If p = 2p0, q = 2q0, k = 2k0, ` = 2`0 are all even numbers, then p0 + q0 =
a + 2, k0 + `0 = b + 2, where p0, q0, k0, `0 ≥ 2. For any choice of p0 and k0 such that
T. Pisanski: Counting edge-transitive, one-ended, three-connected planar maps. . . 177
2 ≤ p0 ≤ (a + 2)/2 and 2 ≤ k0 ≤ (b + 2)/2 we obtain a different tessellation. For
a given divisor a of t there are ba/2cbb/2c choices. Therefore the total number of such
tessellations is given by:
N1(t) :=
∑
a|t
ba/2cbt/(2a)c
Case 2. Here k = ` is an even integer. In this case b = k − 2 is even. There are two
subcases.
Case 2.1. First we determine the number of admissible edge-symbols with p + q odd. In
this case r = 2a = p+ q − 4 is an odd divisor of t and the number of such tessellations is
given by the formula:
N21(t) :=
∑
r|t,r odd
(r − 1)/2.
Case 2.2. In this case both p and q are odd. This can happen only if t is even. In the
following formula for N22, the first summation covers the case p 6= q while the second one
counts the admissible edge symbols with p = q.
N22(t) :=
{
0 if t is odd,∑
r|(t/2)bt/(4r)c+
∑
r|t,r odd 1 if t is even.
Case 3. Due to the symmetry, the counts are the same as in Case 2:
N31(t) = N21(t), N32(t) = N22(t).
Case 4. Finally, we determine the number of admissible edge-symbols with k = ` and
p = q, all odd. This can happen only in case t is odd.
N4(t) :=
{
0 if t is even,∑
r|t 1 if t is odd.
Hence:
N(t) = N1(t) + 2N21(t) + 2N22(t) +N4(t)
where N1(t), N21(t), N22(t), and N4(t) are expressed as summations above. After some
algebraic computations the result follows. In these computations we use the results of
Lemma 3.2.
Lemma 3.2. The numbers N1(t), N2(t), N3(t), N4(t) of planar edge-transitive tessella-
tions with parameter t, satisfying one of the conditions 1–4 of the Proposition 2.1 are given
by:
(1a) N1(t) = t4σ0(t/4) +
t
2 (σ
o
0(t)− σo−1(t)), if t is divisible by 4.
(1b) N1(t) = t2 (σ
o
0(t)− σo−1(t)), if t is even but t2 is odd.
(1c) N1(t) = t+14 σ0(t)−
1
2σ1(t), if t is odd.
(2.1) N21(t) = 12 (σ
o
1(t)− σo0(t)).
(2.2a) N22(t) = σ1( t4 ) +
1
2 (σ
o
1(t) + σ
o
0(t)), if t is divisible by 4.
(2.2b) N22(t) = 12 (σ
o
1(t) + σ
o
0(t)), if t is even but
t
2 is odd.
(2.2c) N22(t) = 0, if t is odd.
178 Ars Math. Contemp. 2 (2009) 173–180
(3.1) N31(t) = 12 (σ
o
1(t)− σo0(t)).
(3.2a) N32(t) = σ1( t4 ) +
1
2 (σ
o
1(t) + σ
o
0(t)), if t is divisible by 4.
(3.2b) N32(t) = 12 (σ
o
1(t) + σ
o
0(t)), if t is even but
t
2 is odd.
(3.2c) N32(t) = 0, if t is odd.
(4a) N4(t) = 0, if t is divisible by 4.
(4b) N4(t) = 0, if t is even but t2 is odd.
(4c) N4(t) = σ0(t), if t is odd;
where N2(t) = N21(t) + N22(t), N3(t) = N31(t) + N32(t), and N(t) = N1(t) +
N2(t) +N3(t) +N4(t) = N1(t) + 2N2(t) +N4(t).
Proof. The cases (2.2c), (4a) and (4b) are obtained by inspection. Case (4c) follows from
the fact that for t odd by definition N4(t) =
∑
a|t 1 = σ0(t). Cases (3.1), (3.2a),(3.2b) and
(3.2c) follow by symmetry from the corresponding cases (2.1), (2.2a),(2.2b) and (2.2c).
Hence we are only left with non-trivial cases (1a),(1b),(1c),(2.1),(2.2a),(2.2b) and (2.2c).
We show how to do case (1c), the rest follows along the same line of reasoning. Recall that
N1(t) =
∑
a|t
ba/2cbt/(2a)c
We may split the summation into 4 parts: the one (i) in which both a and b = t/a are
even,(ii) a even, b odd, (iii) a odd, b even and (iv) both a and b odd. The first case (i)
is non-zero only if t is divisible by four, the second (ii) and third (iii) are equal and are
non-zero only if t is even while the last case (iv) is non-zero only if t is odd. For t odd we
readily get
N1(t) =
∑
a|t
((a− 1)/2)((t/a− 1)/2) =
∑
a|t
(t− t/a− a+ 1)/4.
It is not hard to deduce the result (1c) N1(t) = t+14 σ0(t)−
1
2σ1(t) for t odd. Note that (i)
contributes only to (1a) while (ii) contributes both to (1a) and (1b).
Using this result it is now possible to produce a table.
t 1 2 3 4 5 6 7 8 9 10 11 12 . . .
N(t) 1 2 4 5 6 10 8 12 14 16 12 26 . . .
This table is useful in computing the number of edge-transitive tessellations with a
given growth rate.
Corollary 3.3. The number of planar edge-transitive tessellations an with the n-th growth
rate is determined by: an = N(n+ 3), n ≥ 1.
Proof. Note that n = 1 corresponds to the Euclidean case, n = 2 to the hyperbolic case
with the minimal growth, etc. This seemingly trivial consequence of Theorem 3.1 has a
subtle twist, since not all tessellations for a given parameter t ≥ 4 have the same growth
rate G(t). Exactly two of them, namely 〈3, t − 1; 4, 4〉 and its dual 〈4, 4; 3, t − 1〉, have
growth rateG(t−1). This is due to the fact that these two tessellations have non-concentric
Bilinski diagrams. But the total number remains N(t), since we lose two tessellations at
level t, but gain two similar tessellations at level t + 1. The argument therefore works for
all infinite tessellations. The finite ones are counted separately.
T. Pisanski: Counting edge-transitive, one-ended, three-connected planar maps. . . 179
Using the formula that follows from Theorem 3.1 and Corollary 3.3 one can now con-
struct the table that counts the number of non-isomorphic tessellations with a given growth
rate. Here we list the smallest values of the sequence an together with the corresponding
growth rates.
n 0 1 2 3 4 5 6 7 8 . . .
an 9 5 6 10 8 12 14 16 12 . . .
Γn − 1 2.61803 3.73205 4.79129 5.82843 6.85410 7.87298 8.88748 . . .
It is natural to look for a positive constant c and a suitable function f(t) such that for any
integer t > 2 the function N(t) may be bounded: t ≤ N(t) ≤ ctf(t). Our result expresses
N(t) as a sum of several divisor functions. In order to determine the correct asymptotic
value we need to find the one with the largest growth. Gronwall’s theorem states that
lim supn→∞ σ1(n)/n ln lnn = eγ , where γ is Euler’s constant; see [6]. This suggested
that f(t) = ln ln t. For 3 ≤ t ≤ 100000 one can take c = 4/(3 ln(ln 3)) < 15. However,
for large values of t this inequality does not hold, actually, it fails badly, as pointed out by
one referee. The upper bound with c = 15 is violated, for instance, for t = 2300. A more
reasonable bound seems to hold for f(t) = ln t. This bound may be derived, for instance,
for t = pk, where p is a prime. Whether this bound is indeed the correct upper bound for
any integer t→∞ remains to be proved.
4 Acknowledgements
The author would like to thank Steve Graves and Mark Watkins for valuable remarks,
to the referees for considerably improving the presentation, and to Karin Cvetko Vah for
proofreading the formulae.
References
[1] S. Bilinski, Homogene mreže ravnine, Rad Jugoslav. Akad. Znanosti i Umjetnosti 271 (1948),
145–255.
[2] S. Bilinski, Homogene Netze der Ebene, Bull. Internat. Acad. Yougoslave. Cl. Sci. Math. Phys.
Tech. (N.S.) 2 (1949), 63–111.
[3] J. A. Bruce and M. E. Watkins, Concentric Bilinski diagrams, Australasian J. Combin. 30
(2004), 161–174.
[4] J. E. Graver and M. E. Watkins, Locally Finite, Planar, Edge-Transitive Graphs, Memoirs of the
Amer. Math. Soc. 126 (1997), no. 601.
[5] S. Graves, T. Pisanski and M. E. Watkins, Growth of Edge-Homogeneous Tessellations, SIAM
J. Discrete Math. 23 (2008), 1–18.
[6] T. H. Gronwall, Some Asymptotic Expressions in the Theory of Numbers, Trans. Amer. Math.
Soc. 14 (1913), 113–122.
[7] B. Grünbaum and G. C. Shephard, Edge-transitive planar graphs, J. Graph Theory 11 (1987),
141–155.
[8] B. Grünbaum and G. C. Shephard, Tilings and Patterns, W. H. Freeman and Company, New
York, 1987.
[9] J. F. Moran, The growth rate and balance of homogeneous tilings in the hyperbolic plane,
Discrete Math 173 (1997), 151–186.
180 Ars Math. Contemp. 2 (2009) 173–180
[10] P. Niemeyer and M. E. Watkins, Geodetic rays and fibers in one-ended planar graphs. J. Com-
bin. Theory B 69 (1997), 142–163.