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 xed non saturated polyhexes and polyiamonds.
We discuss the concept of saturated and non saturated polyforms and polycubes [BCGS17] in Sections 4 and 5 where we exhibit three bijections. The rst 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 xed fully leafed tree-like polyhexes and polyiamonds. These families of polyforms are induced subtrees of in nite 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 Let G = (V; E) be a simple graph, u 2 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 in nite sainmdpdleisgtriaspthheG2E=uc(liZd2e;aAn4d),iswtahnecree oAf4Ris2.thFeor4-aandyjapce2ncZy2r,eltahteiosnetdce(pn)e=d bfyp0A24 R=2fj(pd;ispt01)2(pZ;p20 )j dist1(=p2;gp,0)w=he1rge dist1 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 nite 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 xed 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 de nitions of cell, grounded polyomino, xed 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 nite simple non empty tree. A vertex u 2 V is a leaf of T when degT (u) = 1 and is an inner vertex otherwise. For any d 2 N, the number of vertices of degree d is denoted by nd(T ) and n(T ) = jV j is the number of vertices of T which is also called the size of T .
A (grounded, xed or free) tree-like polyform (resp. polycube) is therefore a (grounded, xed or free) polyform (resp. polycube) whose associated graph is a tree. We now introduce rooted grounded tree-like polyforms and polycubes.
De nition 2.1. A rooted grounded tree-like polyform or polycube in a lattice that (i) T = (V; E) is a grounded tree-like polyform or polycube of size at least 2; (ii) r# 2 V , called the root of R, is a cell of T ; # (iii) u 2 ,# 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- nal. Otherwise R is called nal.
# #
If R = (T; r; u ) is a rooted, groun#ded, non- nal tree-like polyform or polycube, a unit vector v 2 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.
# # De nition 2.2 (Graft union). Let R = (T; r; u ) a#nd R0 = (T 0; r0; u0) be rooted grounded non- nal tree-like polyforms or polycubes in the lattice such that u0 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 = (Z3[V [ (V 0)]; r; u ); # is a triple R = (T; r; u ) such where V , V 0 are the respective sets of vertices of T , T 0 and
The graft union is naturally extended to xed and free tree-like polyforms and polycubes. # is the translation with respect to the vector r0r # u0.
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, polyhexes and polyiamonds. Then we have
Lsqu(n) = Lhex(n) = Ltri(n) = 8>2; <
n (2; >:`squ(n
1; `hex(n = j n k + 1 2 if n = 2; if n = 3; 4; 5; 4) + 2; if n 6.
if n = 2; 3; 2) + 1; if n 4. 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
Lcub(n) = 8>fcub(n) + 1; > ><fcub(n); >>fcub(n > :`cub(n if n = 6; 7; 13; 19; 25; if 2 n 40 and n 6= 6; 7; 13; 19; 25; 41) + 28; if 41 n 81; 41) + 28; if n 82. where fcub(n) = 8>b(2n + 2)=3c; if 0 <
b(2n + 3)=3c; if 12 >:b(2n + 4)=3c; if 28 n n n 11; 27; 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 satis es the surprising ratio Lcub(n) 28n=41. 4
Let L denote any of the four leaf functions described in (1), (2) and (3). Since L (n) satis es 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 in nitely 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 de ned 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 di cult 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). (1) (2) (3) $ (a) T (b) I(T )
(c) squ(T ) Theorem 4.1 (Cross operator, [BCGS17]). There exists a bijection squ from 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: Tsqu(k)
sq!u STsqu(4k + 1):
The bijection squ is illustrated in Figure 1 and it informs us that the complexity of counting saturated treelike 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 xed saturated tree-like polyiamonds to free and xed saturated polyhexes.
Proof. (sketch). shown in Figure 5.
The correspondance is established by simply truncating the triangles to form hexagons, as 5
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.
= 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 xed 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 xed fully leafed polyhexes T which are the concatenation T = T1xT2 with T1 2 Ct(j), T2 2 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 f lhext(2k + 3) = X ct(j)ct(k
j) j=0 b(k 1)=2c
X 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 xed polyhexes T where x is adjacent to a leaf of T2 2 Ct(k) (Figure 6 (a)(i)) and 6k polyhexes where x is adjacent to an inner cell of T2 2 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 xed polyhexes where a leaf of T2 2 Ct(k 1) is adjacent to x (Figure 6(b)(iii)) and 6(k 3) polyhexes where an inner cell of T2 2 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 xed polyhexes where either a leaf of T2 2 Ct(k 2) or a cell y 2 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 xed polyhexes (Figure 6(e) and (d)(xi)). This count includes a particular polyhex T1 2 Ct(4), shown in Figure 6(d)(xi), that is not a path. When 5 j k j, special con gurations 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 ct(j)ct(k j) = [60 + 6k] + [48 + 6(k (b) For k < 9, the values ct(j)ct(k j) are di erent 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. (i) (ii) (iii) (iv) (v) (vi)
Proposition 5.2. For k 0, the number f ltrit(2k + 3) of xed, fully leafed polyiamonds trees of odd size 2k + 3 is given by the following expressions:
k fltrit(2k + 3) Proof. First notice that these polyiamonds have exactly one cell of degree 2 denoted x. We enumerate polyiamonds by exhibiting a set P of seven basic polyiamonds, each made of an inner set of cells of degree 3, to be adjacent to x. These 7 polyamonds types are shown in Figure 7. Three of these polyiamonds have a variable size and they appear in Figure 7 (E); (F ); (G). The black thicker segment appearing in each polyiamond of Figure 7 marks the cell of the polyiamond that is to be adjacent to the cell x of degree 2.
We claim that every fully leafed non saturated tree-like polyiamond is obtained by choosing a pair of structures and by positioning them adjacent to x. In order to avoid duplication of cases, we assume that structures F and G contain respectively at least three and four cells of degree three.
For instance, the pair fD; F g generates 12 xed polyiamonds of size 2k + 3 for any k 7, one of which, of size n(T ) = 19, is illustrated in Figure 8. The enumeration of these non saturated polyamonds is done by nding the number of xed polyiamonds that are obtained with every pair fX; Y g. These values are presented in Table 2. The numbers f ltrit(2k + 3) of non saturated polyiamonds presented in Table 1 are obtained from Table 2.
The enumeration of polyhexes and polyiamonds presented in Propositions 5.1 and 5.2 have been independently veri ed with computer programs that iteratively enumerate non saturated tree-like polyforms of size n by repeatedly grafting cells of degree three to a cell of degree two [deC18]. We know from the degree distribution of the inner cells of non saturated polyiamonds that all fully leafed tree-like polyhexes and polyiamonds can be k = 0 (A) k = 1 (B)
. . . k
3 (F) obtained this way. Indeed, since non saturated polyiamonds have one cell x of degree two and k cells of degree three, all these polyiamonds can be obtained by the graft of cells of degree three one at a time. 6
The next step in the enumeration of fully leafed polyforms and polycubes is the enumeration of non saturated polyominoes and polycubes and also of saturated polycubes. In the context of enumeration of families of polyforms and polycubes, we have shown that bijections can be used to give an evaluation of the complexity of the problems. For instance, we know that the enumeration of saturated polyominoes of size 4k + 1 is precisely equivalent to the enumeration of tree-like polyominoes of size k. It would certainly be interesting to have a similar result for the enumeration of saturated tree-like polycubes.