=Paper=
{{Paper
|id=Vol-2113/paper11
|storemode=property
|title=Non saturated polyhexes and polyiamonds
|pdfUrl=https://ceur-ws.org/Vol-2113/paper11.pdf
|volume=Vol-2113
|authors=Alexandre Blondin Massé,Julien de Carufel,Alain Goupil
|dblpUrl=https://dblp.org/rec/conf/gascom/MasseCG18
}}
==Non saturated polyhexes and polyiamonds==
https://ceur-ws.org/Vol-2113/paper11.pdf
Non saturated polyhexes and polyiamonds
Alexandre Blondin Massé
Laboratoire de combinatoire et d’informatique mathématique
Université du Québec à Montréal
blondin masse.alexandre@uqam.ca
Julien de Carufel Alain Goupil
Université du Québec à Trois-Rivières Université du Québec à Trois-Rivières
Trois-Rivières, Canada Trois-Rivières, Canada
Julien.de.carufel@uqtr.ca Alain.Goupil@uqtr.ca
Abstract
Induced subtrees of a graph G are induced subgraphs of G that are
trees. Fully leafed induced subtrees of G have the maximal number of
leaves among all induced subtrees of G. In this extended abstract we
are investigating the enumeration of a particular class of fully leafed
induced subtrees that we call non saturated. After an overview of this
recent subject, we proceed to the enumeration of fixed non saturated
polyhexes and polyiamonds.
1 Introduction
We recently presented a new family of combinatorial and graph theoretic structures called fully leafed induced
subtrees of a simple graph G of size n which are induced subtrees of a graph G with a maximal number of
leaves [BCGS17]. Fully leafed induced subtrees are realized as polyforms in two-dimensional regular lattices and
polycubes in the three dimensional cubic lattice so that tree-like polyforms of size n are fully leafed when they
contain the maximum number of leaves among all tree-like polyforms of size n. Recursive and exact expressions
were given in [BCGS17, BCGLNV18] for the number of leaves in a number of particular cases which include
graphs and polyforms.
We also showed in [BCGLNV18] that the problem of deciding if there exists an induced subtree with i vertices
and ` leaves in a simple graph G of size n is NP-complete in general. We define the map LG : N → N by the
condition that LG (n) is the maximal number of leaves among all induced subtrees of G of size n. We call this
map the leaf function of G. We have computed the values of the map LG for some classical graphs and we have
described in [BCGLNV18] a branch-and-bound algorithm that computes the function LG for any simple graph
G. In [BCGLNV18], we consider the problem of deciding wether a given sequence (`0 , `1 , . . . , `n ) of natural
numbers is the leaf sequence (LG (n))n of some graph G. We call this problem the leaf realization problem. In
the particular case where G is a caterpillar, a bijection [BCGLNV18] was exhibited between the set of discrete
derivatives of the leaf sequences (LG (i))3≤i≤|G| and the set of prefix normal words introduced in [FL11] and
investigated in [BFLRS14, BFLRS17].
Copyright © by the paper’s authors. Copying permitted for private and academic purposes.
In: L. Ferrari, M. Vamvakari (eds.): Proceedings of the GASCom 2018 Workshop, Athens, Greece, 18–20 June 2018, published at
http://ceur-ws.org
116
We discuss the concept of saturated and non saturated polyforms and polycubes [BCGS17] in Sections 4
and 5 where we exhibit three bijections. The first bijection relates the set Tsqu (k) of tree-like polyominoes of
size k and the set STsqu (4k + 1) of saturated tree-like polyominoes of size 4k + 1. The second bijection maps
the set SThex (n) of saturated polyhexes of size n to the set STtri (n) of saturated polyiamonds of size n. The
third bijection is between the set STcub (41k + 28) of saturated tree-like polycubes of size 41k + 28 and the set
4Ti (3k + 2) of 4-trees that are polycubes of size 3k + 2 recently introduced [BCG18].
In this extended abstract, we are interested with the enumeration of fixed fully leafed tree-like polyhexes and
polyiamonds. These families of polyforms are induced subtrees of infinite regular lattices λ and their leaf function
is denoted by Lλ (n).
It was already shown in [BCGS17] that saturated tree-like polyhexes and polyiamonds are easy to enumerate.
They both are caterpillars with a linear shape and there is in fact a bijective correspondance between these two
sets. The description of non saturated tree-like polyhexes and polyiamonds is more intricate and we now focus
on their enumeration.
2 Polyforms, Polycubes and Graphs
Let G = (V, E) be a simple graph, u ∈ V and U ⊆ V . For any subset U ⊆ V , the subgraph induced by U is the
graph G[U ] = (U, E ∩ P2 (U )), where P2 (U ) is the set of 2-elements subsets of V . The square lattice is the infinite
simple graph G2 = (Z2 , A4 ), where A4 is the 4-adjacency relation defined by A4 = {(p, p0 ) ∈ Z2 | dist(p, p0 ) = 1}
and dist is the Euclidean distance of R2 . For any p ∈ Z2 , the set c(p) = {p0 ∈ R2 | dist∞ (p, p0 ) ≤ 1/2}, where
dist∞ is the uniform distance of R2 , is called the square cell centered in p. The function c is naturally extended
to subsets of Z2 and subgraphs of G2 . For any finite subset U ⊆ Z2 , we say that G2 [U ] is a grounded polyomino
if it is connected. The set of all grounded polyominoes is denoted by GP. Given two grounded polyominoes
P = G2 [U ] and P 0 = G2 [U 0 ], we write P ≡t P 0 (resp. P ≡i P 0 ) if there exists a translation T : Z2 → Z2 (resp.
an isometry I on Z2 ) such that U 0 = T (U ) (resp. U 0 = I(U )). A fixed polyomino (resp. free polyomino) is then
an element of GP/ ≡t (resp. GP/ ≡i ). Clearly, any connected induced subgraph of G2 corresponds to exactly
one connected set of square cells via the function c. Consequently, from now on, polyominoes will be considered
as simple graphs rather than sets of edge-connected square cells.
All definitions of cell, grounded polyomino, fixed polyomino and free polyomino in the above paragraph are
extended to the hexagonal lattice with the 6-adjacency relation, the triangular lattice with the 3-adjacency relation
and the cubic lattice with the 6-adjacency relation. Grounded polyforms and polycubes are thus connected
subgraphs of regular grids and the terminology of graph theory becomes available. Let T = (V, E) be any finite
simple non empty tree. A vertex u ∈ V is a leaf of T when degT (u) = 1 and is an inner vertex otherwise. For
any d ∈ N, the number of vertices of degree d is denoted by nd (T ) and n(T ) = |V | is the number of vertices of
T which is also called the size of T .
A (grounded, fixed or free) tree-like polyform (resp. polycube) is therefore a (grounded, fixed or free) polyform
(resp. polycube) whose associated graph is a tree. We now introduce rooted grounded tree-like polyforms and
polycubes.
Definition 2.1. A rooted grounded tree-like polyform or polycube in a lattice λ is a triple R = (T, r, #» u ) such
that
(i) T = (V, E) is a grounded tree-like polyform or polycube of size at least 2;
(ii) r ∈ V , called the root of R, is a cell of T ;
(iii) #»
u ∈ λ, called the direction of R, is a unit vector such that r + #»
u is a cell of T adjacent to r.
When r + #» u is a leaf of T , we say that R is non-final. Otherwise R is called final.
If R = (T, r, #»
u ) is a rooted, grounded, non-final tree-like polyform or polycube, a unit vector #»v ∈ λ is called
a free direction of R whenever r − #» v is a leaf of T . We now introduce the operation called the graft union of
tree-like polyforms and polycubes.
#»
Definition 2.2 (Graft union). Let R = (T, r, #» u ) and R0 = (T 0 , r0 , u0 ) be rooted grounded non-final tree-like
#»0
polyforms or polycubes in the lattice λ such that u is a free direction of R. The graft union of R and R0 ,
whenever it exists, is the rooted grounded tree-like polyform or polycube
R / R0 = (Z [V ∪ τ (V 0 )], r, #»
3 u ),
# » #»
where V , V are the respective sets of vertices of T , T and τ is the translation with respect to the vector r0 r − u0 .
0 0
The graft union is naturally extended to fixed and free tree-like polyforms and polycubes.
117
3 Fully leafed polyforms and polycubes
The leaf function Lλ (n), giving the maximal number of leaves in an induced subtree of size n, ihas been established
for all planar regular grids λ i.e. for polyominoes, polyhexes and polyiamonds and also for polycubes.
Theorem 3.1 ([BCGS17]). Let Lsqu , Lhex and Ltri denote respectively the leaf functions of polyominoes, poly-
hexes and polyiamonds. Then we have
2,
if n = 2;
Lsqu (n) = n − 1, if n = 3, 4, 5; (1)
`squ (n − 4) + 2, if n ≥ 6.
(
2, if n = 2, 3;
Lhex (n) = Ltri (n) = (2)
`hex (n − 2) + 1, if n ≥ 4.
jnk
= +1
2
and the asymptotic growth of Lλ is given by Lλ (n) ∼ n/2 for the three families λ of tree-l9ke polyforms.
The proof that these expressions are exact is based on (i) the construction of families of polyforms that satisfy
Equations (1) and (2); (ii) the elimination of all possible branches that would belong to a tree-like polyform of
minimal size with more leafs than Lλ (n).
In the case of three dimensional polycubes, the leaf function is more intricate.
Theorem 3.2 ([BCGS17]). Let Lcub be the leaf-function on the cubic lattice. Then
fcub (n) + 1, if n = 6, 7, 13, 19, 25;
f (n),
cub if 2 ≤ n ≤ 40 and n 6= 6, 7, 13, 19, 25;
Lcub (n) = (3)
fcub (n − 41) + 28, if 41 ≤ n ≤ 81;
`cub (n − 41) + 28, if n ≥ 82.
b(2n + 2)/3c, if 0 ≤ n ≤ 11;
where fcub (n) = b(2n + 3)/3c, if 12 ≤ n ≤ 27;
b(2n + 4)/3c, if 28 ≤ n ≤ 40.
The proof of this fact uses the same argument than in the two dimensional case but the set of possible branches
in a tree-like polycube of size n that would have more leaves than Lcub (n) is larger and it must be established
with a computer program that exhausts all possibilities. The asymptotic growth of Lcub is still linear but it
satisfies the surprising ratio Lcub (n) ∼ 28n/41.
4 Saturated polyforms and polycubes
Let Lλ denote any of the four leaf functions described in (1), (2) and (3). Since Lλ (n) satisfies a linear recurrence,
it is immediate that there exists two parallel linear functions Lλ , Lλ and a positive integer n0 such that
Lλ (n) ≤ Lλ (n) ≤ Lλ (n), for n ≥ n0 ,
if we add the constraint that there must exist infinitely many positive integers n > 0 for which Lλ (n) = Lλ (n)
and Lλ (n) = Lλ (n), then the functions Lλ (n) and Lλ (n) become unique. Saturated tree-like polyforms and
polycubes are defined as those tree-like polyforms and polycubes T for which n1 (T ) ≥ L(n(T )).
Sets of saturated tree-like polyforms and polycubes possess structural properties that allow their bijective
reduction to simpler polyforms and polycubes. These bijections are, to our actual knowledge, lattice dependent
and are useful in the enumeration of saturated tree-like polyforms. We describe these bijections in the following
paragraphs.
The upper bounding linear function of saturated polyominoes is Lsqu (n) = (n + 3)/2. For integers k ≥ 1,
saturated tree-like polyominoes T have size n(T ) = 4k + 1 and n1 (T ) = 2k + 2 leaves. It is not difficult to show
that saturated tree-like polyominoes are the iterated graft union of copies of a unique tile of size 5 made of one
cell of degree 4 and four leaves that we call a cross because of its shape (see Figure 2).
118
↔ ↔
(a) T (b) I(T ) (c) φsqu (T )
Figure 1: The bijection φsqu for tree-like polyominoes
=
Figure 2: Saturated tree-like polyomino as graft union of crosses
Theorem 4.1 (Cross operator, [BCGS17]). There exists a bijection φsqu from the set Tsqu (k) of tree-like poly-
ominoes of size k and the set STsqu (4k + 1) of saturated tree-like polyominoes of size 4k + 1:
φsqu
Tsqu (k) −−−→ STsqu (4k + 1).
The bijection φsqu is illustrated in Figure 1 and it informs us that the complexity of counting saturated tree-
like polyominoes of size 4k + 1 is identical to the complexity of the enumeration of tree-like polyominoes of size
k.
Theorem 4.2 (Geometric shape of saturated polyhexes and polyiamonds, [BCGS17]). Each saturated polyhex
(resp. polyiamond) is the successive graft union of crosses in the hexagonal (resp. triangular) lattice.
Proof. This result is immediate from the facts that graft union preserves degree distribution, that saturated
polyhexes and polyiamonds have cells of degree 3 and 1 and that a cross is the only elementary polyform which
contains a cell of degree 3. See Figures 3 and 4 for an illustration.
Proposition 4.3 ([BCG18]). There exists a bijection from, respectively, free and fixed saturated tree-like polyi-
amonds to free and fixed saturated polyhexes.
Proof. (sketch). The correspondance is established by simply truncating the triangles to form hexagons, as
shown in Figure 5.
5 Non saturated polyhexes and polyiamonds
The description of nonsaturated polyforms is more intricate than the saturated case because there is more
freedom in the choice of the position of “extra cells“. At the moment, we are only able to enumerate polyhexes
and polyiamonds. We leave the enumeration of fully leafed non saturated tree-like polyominoes and polycubes
as open problems.
=
Figure 3: A saturated tree-like polyiamond as graft union of crosses
119
=
Figure 4: Saturated tree-like polyhexes as graft union of crosses
Figure 5: Bijection from satured polyiamonds to saturated polyhexes.
k 0 1 2 3 4 5 6 7 8 k≥9
f lhext (2k + 3) 9 18 45 102 180 246 327 426 516 36 + 78(k − 2)
Proposition 5.1. For k ≥ 0, the number f lhext (2k + 3) of fixed, fully leafed polyhex trees of odd size 2k + 3 is
given by the following expressions
Proof. The proof is the result of a case study where special structures appear until the size n(T ) = 19 is reached.
We know already that fully leafed polyhexes of odd size n = 2k + 3 contain k cells of degree three and one cell of
degree two, denoted x. These polyhexes are not saturated. As shown in Figure 6, the cell x partitions the k cells
of degree three of a fixed fully leafed polyhex T in two disjoint connected sets T1 , T2 of respective sizes j ≥ 0
and k − j ≥ 0. Both sets have one cell adjacent to x and both sets are, with one exception, forming a path. We
denote by Ct (j) the set of all paths of cells of degree 3 of length j. Furthermore we denote by Ct (j)Ct (k − j)
the set of fixed fully leafed polyhexes T which are the concatenation T = T1 xT2 with T1 ∈ Ct (j), T2 ∈ Ct (k − j)
and we denote by ct (j)ct (k − j) the cardinality of Ct (j)Ct (k − j). Clearly we have
bk/2c
X
f lhext (2k + 3) = ct (j)ct (k − j)
j=0
In order to obtain f lhext (2k + 3), we evaluate each term ct (j)ct (k − j) and provide a general expression when
it exists.
First, we look at the case Ct (0)Ct (k) shown in Figure 6(a). For all k ≥ 5, there are 60 fixed polyhexes T
where x is adjacent to a leaf of T2 ∈ Ct (k) (Figure 6 (a)(i)) and 6k polyhexes where x is adjacent to an inner
cell of T2 ∈ Ct (k) (Figure 6 (a)(ii)). These cover all cases in the set Ct (0)Ct (k) and we have ct (0)ct (k) = 60 + 6k
for k ≥ 5.
In the case Ct (1)Ct (k − 1), there are 48 fixed polyhexes where a leaf of T2 ∈ Ct (k − 1) is adjacent to x (Figure
6(b)(iii)) and 6(k − 3) polyhexes where an inner cell of T2 ∈ Ct (k − 1) is adjacent to x and k ≥ 6 (Figure
6(b)(iv)). In the case Ct (2)Ct (k − 2), k ≥ 7, there are 72 fixed polyhexes where either a leaf of T2 ∈ Ct (k − 2)
or a cell y ∈ T2 next to a leaf is adjacent to x (Figure 6(c)(v) and (vi)). In the set Ct (3)Ct (k − 3), k ≥ 8, a
case study shows that there are ct (3)ct (k − 3) = 132 polyhexes (Figure 6(d)(vii-x)). When 4 = j < k − j, there
are 180 fixed polyhexes (Figure 6(e) and (d)(xi)). This count includes a particular polyhex T1 ∈ Ct (4), shown
in Figure 6(d)(xi), that is not a path. When 5 ≤ j ≤ k − j, special configurations disappear and there are 66
polyhexes where 5 ≤ j = k − j and 132 polyhexes with 5 ≤ j < k − j. Summing all the previous cases for k ≥ 9,
we obtain
b(k−1)/2c
X
ct (j)ct (k − j) = [60 + 6k] + [48 + 6(k − 3)] + [72] + [132]
j=0
b(k−1)/2c
X
+ [180] + [132] + 132 + 66χ(k is even)
j=5
= 36 + 78(k − 2), k ≥ 9.
(b) For k < 9, the values ct (j)ct (k − j) are different from the general cases described above for a number of
reasons that forbid their inclusion in a general setting. There is no space here for this analysis.
120
(i) (ii) (iii) (iv) (v) (vi)
(a) ct (0)ct (k) = 60 + 6k (b) ct (1)ct (k − 1) = 30 + 6k (c) ct (2)ct (k − 2) = 72
k≥5 k≥6 k≥7
(vii) (viii) (ix) (x)
(d) ct (3)ct (k − 3) = 132
k≥8
(xi)
(e) ct (4)ct (k − 4) = 180 (f) ct (j)ct (j) = 66 (g) ct (j)ct (k − j) = 132
k≥9 j≥5 5≤j