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.
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 L G : N → N by the condition that L G (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 L G for some classical graphs and we have described in [BCGLNV18] a branch-and-bound algorithm that computes the function L G 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 (L G (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 (L G (i)) 3≤i≤|G| and the set of prefix normal words introduced in [FL11] and investigated in [BFLRS14,BFLRS17].
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 T squ (k) of tree-like polyominoes of size k and the set ST squ (4k + 1) of saturated tree-like polyominoes of size 4k + 1. The second bijection maps the set ST hex (n) of saturated polyhexes of size n to the set ST tri (n) of saturated polyiamonds of size n. The third bijection is between the set ST cub (41k + 28) of saturated tree-like polycubes of size 41k + 28 and the set 4T i (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.
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 ∩ P 2 (U )), where P 2 (U ) is the set of 2-elements subsets of V . The square lattice is the infinite simple graph G 2 = (Z 2 , A 4 ), where A 4 is the 4-adjacency relation defined by
, where dist ∞ is the uniform distance of R 2 , is called the square cell centered in p. The function c is naturally extended to subsets of Z 2 and subgraphs of G 2 . For any finite subset U ⊆ Z 2 , we say that G 2 [U ] is a grounded polyomino if it is connected. The set of all grounded polyominoes is denoted by GP. Given two grounded polyominoes P = G 2 [U ] and P = G 2 [U ], we write P ≡ t P (resp. P ≡ i P ) if there exists a translation T : Z 2 → Z 2 (resp. an isometry I on Z 2 ) such that U = T (U ) (resp. U = I(U )). A fixed polyomino (resp. free polyomino) is then an element of GP/ ≡ t (resp. GP/ ≡ i ). Clearly, any connected induced subgraph of G 2 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 deg T (u) = 1 and is an inner vertex otherwise. For any d ∈ N, the number of vertices of degree d is denoted by n d (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;
) 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 R = (T , r , #» u ) be rooted grounded non-final tree-like polyforms or polycubes in the lattice λ such that #» u is a free direction of R. The graft union of R and R , whenever it exists, is the rooted grounded tree-like polyform or polycube
where V , V are the respective sets of vertices of T , T and τ is the translation with respect to the vector
The graft union is naturally extended to fixed and free tree-like 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.
). Let L squ , L hex and L tri denote respectively the leaf functions of polyominoes, polyhexes and polyiamonds. Then we have
(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.
). Let L cub be the leaf-function on the cubic lattice. Then
if 2 ≤ n ≤ 40 and n = 6, 7, 13, 19, 25;
(3)
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 L cub (n) is larger and it must be established with a computer program that exhausts all possibilities. The asymptotic growth of L cub is still linear but it satisfies the surprising ratio L cub (n) ∼ 28n/41.
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 n 0 such that
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 n 1 (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 L squ (n) = (n + 3)/2. For integers k ≥ 1, saturated tree-like polyominoes T have size n(T ) = 4k + 1 and n 1 (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).
). There exists a bijection φ squ from the set T squ (k) of tree-like polyominoes of size k and the set ST squ (4k + 1) of saturated tree-like polyominoes of size 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.
). There exists a bijection from, respectively, free and fixed saturated tree-like polyiamonds 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.
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. Proposition 5.1. For k ≥ 0, the number f lhex t (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 T 1 , T 2 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 C t (j) the set of all paths of cells of degree 3 of length j. Furthermore we denote by C t (j)C t (k − j) the set of fixed fully leafed polyhexes T which are the concatenation
and we denote by c t (j)c t (k − j) the cardinality of C t (j)C t (k − j). Clearly we have
In order to obtain f lhex t (2k + 3), we evaluate each term c t (j)c t (k − j) and provide a general expression when it exists. First, we look at the case C t (0)C t (k) shown in Figure 6(a). For all k ≥ 5, there are 60 fixed polyhexes T where x is adjacent to a leaf of T 2 ∈ C t (k) (Figure 6 (a)(i)) and 6k polyhexes where x is adjacent to an inner cell of T 2 ∈ C t (k) (Figure 6 (a)(ii)). These cover all cases in the set C t (0)C t (k) and we have c t (0)c t (k) = 60 + 6k for k ≥ 5.
In the case C t (1)C t (k − 1), there are 48 fixed polyhexes where a leaf of T 2 ∈ C t (k − 1) is adjacent to x (Figure 6(b)(iii)) and 6(k − 3) polyhexes where an inner cell of T 2 ∈ C t (k − 1) is adjacent to x and k ≥ 6 (Figure 6(b)(iv)). In the case C t (2)C t (k − 2), k ≥ 7, there are 72 fixed polyhexes where either a leaf of T 2 ∈ C t (k − 2) or a cell y ∈ T 2 next to a leaf is adjacent to x (Figure 6(c)(v) and (vi)). In the set C t (3)C t (k − 3), k ≥ 8, a case study shows that there are c t (3)c t (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 T 1 ∈ C t (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) For k < 9, the values c t (j)c t (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. We now proceed to the enumeration of non-saturated tree-like polyiamonds.
Proposition 5.2. For k ≥ 0, the number f ltri t (2k + 3) of fixed, fully leafed polyiamonds trees of odd size 2k + 3 is given by the following expressions: 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 {D, F } generates 12 fixed 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 finding the number of fixed polyiamonds that are obtained with every pair {X, Y }. These values are presented in Table 2. The numbers f ltri t (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 verified 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
Figure 7: The set P of polyiamonds in non saturated fully leafed tree-like polyiamonds Figure 8: A fully leafed polyiamond of size 2k + 3, k ≥ 7.
Table 2: Number of polyiamonds obtained from pairs in the set P 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.
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.