/^creative ^commor ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 12 (2017) 247-260 Independent sets on the Towers of Hanoi graphs* Hanlin Chen, Renfang Wu, Guihua Huang , Hanyuan Deng t College of Mathematics and Computer Science, Hunan Normal University, Changsha, Hunan 410081, P. R. China Received 24 December 2014, accepted 16 May 2016, published online 7 December 2016 Abstract The number of independent sets is equivalent to the partition function of the hardcore lattice gas model with nearest-neighbor exclusion and unit activity. In this article, we mainly study the number of independent sets i(Hn) on the Tower of Hanoi graph Hn at stage n, and derive the recursion relations for the numbers of independent sets. Upper and lower bounds for the asymptotic growth constant ^ on the Towers of Hanoi graphs are derived in terms of the numbers at a certain stage, where ^ = ^(Gf and v(G) is the number of vertices in a graph G. Furthermore, we also consider the number of independent sets on the Sierpinski graphs which contain the Towers of Hanoi graphs as a special case. Keywords: Independent sets, the Tower of Hanoi graph, Sierpinski graph, recursion relation, asymptotic growth constant, asymptotic enumeration. Math. Subj. Class.: 05C30, 05C69 1 Introduction Counting sets satisfying a fixed property in graphs ranges among the classical tasks of combinatorics. There is a vast amount of literatures on this kind of combinatorial problems for various classes of graphs, especially for Sierpinski graphs, by different authors. We note that the set counting problems such as the number of independent sets and the number of matchings have been studied in the past [2, 4, 9, 10, 11, 26, 35, 36]. On one hand, all these graph invariants reflect the structure of a graph in some way, and therefore, some of them are even of interest in theoretical chemistry for the study of molecular graphs (see [32, 38]). For example, the number of independent sets is called * Project supported by the National Natural Science Foundation of China (11401192) and Hunan Provincial Innovation Foundation for Postgraduate (CX2015B162). 1 Corresponding Author. E-mail address: hydeng@hunnu.edu.cn (Hanyuan Deng) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 248 Ars Math. Contemp. 12 (2017) 383-413 Merrifield-Simmons index, the number of matchings is known as Hosoya index in chemistry. It was shown that both correlate well with physicochemical properties of the corresponding molecules (see [23, 30]). On the other hand, the number of independent sets is equivalent to the partition function of the hard-core lattice gas model with nearest-neighbor exclusion and unit activity. The lattice gas with repulsive pair interaction is an important model in statistical mechanics [3, 13, 16, 33]. For the special case with hard-core nearest-neighbor exclusion such that each site can be occupied by at most one particle and no pair of adjacent sites can be simultaneously occupied, the partition function of the lattice gas coincides with the independence polynomial in combinatorics [14, 34]. This model is a problem of interest in mathematics [39, 15, 24]. The growth of the number of independent sets in the m x n grid graph is of interest in statistical physics (see [1]). It is known that the number of independent sets in the m x n grid graph grows with amn, where a = 1.503048082 • • • is the so-called hard square entropy constant. The bound for this constant was successively improved by Weber [40], Engel [9] and Calkin and Wilf [4]. The number of independent sets and its bounds had been considered on various graphs [27, 29, 41]. It is of interest to consider independent sets on self-similar fractal lattices which have scaling invariance rather than translational invariance [35]. The recursion relations for the numbers of independent sets on the Sierpinski gasket were derived by Chang, Chen and Yan [6]. A special type of self-similar graph that has been of interest is the Hanoi graph, which has been extensively studied in several contexts [5, 7, 8, 12, 17, 18, 19, 20, 22, 25, 28, 31]. This graph, which is also known as the Tower of Hanoi graph, came from the well known Tower of Hanoi puzzle, as the graph is associated to the allowed moves in this puzzle. We shall derive the recursion relations for the numbers of independent sets on the Towers of Hanoi graphs. Upper and lower bounds for the asymptotic growth constant a on the Tower of Hanoi graphs are derived in terms of the numbers at a certain stage, where a = '"of, i(G) and v(G) are the number of independent sets and the number of vertices in a graph G, respectively. Furthermore, we also consider the Sierpinski graphs which include the Towers of Hanoi graphs as a special case. 2 Preliminaries We recall some basic definitions about graphs. A graph G = (V, E) with vertex set V and edge set E is always supposed to be undirected, without loops or multiple edges. Vertices x and y are adjacent if xy is an edge in E. Let v(G) = |V| be the number of vertices and e(G) = |E| the number of edges in G. An independent set is a subset of the vertices such that any two of them are not adjacent. When the number ¿(G) of independent sets in G grows exponentially with v(G) as v(G) ^ to, let us define a constant a describing this exponential growth: ln ¿(G) a = lim —-——. v(G)^ 1, Hn is obtained from three copies of Hn-1 joined by three new edges, each one connecting a pair of vertices from two different replicas of Hn-1, as show in Figure 1. From the construction rule, we can find that the number of vertices of Hn is 3n+1 while the number of edges is 3"+22-3. 3 The number of independent sets on Hn In this section, we will derive the asymptotic growth constant for the number of independent sets on the Tower of Hanoi graph Hn in detail. For the Tower of Hanoi graph Hn, in is its number of independent sets, fn is its number of independent sets such that all three outmost vertices are not in the vertex subset, gn is its number of independent sets such that only one specified vertex of three outmost vertices is in the vertex subset, hn is its number of independent sets such that exact two specified vertices of the three outmost vertices are in the vertex subset, pn is its number of independent sets such that all three outmost vertices are in the vertex subset. They are illustrated in Figures 2-5, where only the outmost vertices are shown and a solid circle is in the independent set and an open circle is not. Because of rotational symmetry, there are three possible gn and three possible hn such that in = fn + 3gn + 3hri + Pn and fo = go = 1, ho = po = 0, io = fo + 3go + 3ho + po = 4. 260 Ars Math. Contemp. 12 (2017) 383-413 Lemma 3.1. For any nonnegative integer n, we have /n+i =/n+6/n gn+3/nh„+9/„gn+6/ g„h„+2gn, 0 0 0 0 0 Q gn+1 =/ngn + 22/nkn + /nPn + 4/ngn + 8/ngnhn + 2/ngnPn + 2/nhi + 3gn + 4gn hn, O O Q O O hn+i =/ngn + 4/ngnhn + 2/ngnPn + 3/n kri + 2/nhnPn + 2gn + 7gn K + 2gnPn +4gnhn, Pn+1 =gn + 6g2hn + 3gn^n + 9gnhn + 6gnh„Pn + 2hn. Proof. Note that the number /n+1 consists of (i) one configuration where all three Hn belong to the class that enumerated by /n; (ii) six configurations where one of the Hn belongs to the class that enumerated by gn and the other two belong to the class that enumerated by /n; (iii) three configurations where one of the Hn belongs to the class that enumerated by hn and the other two belong to the class that enumerated by /n; (iv) nine configurations where one of the Hn belongs to the class that enumerated by /n and the other two belong to the class that enumerated by gn ; (v) six configurations where all three Hn belong to the class that enumerated by /n, gn and hn, respectively; (vi) two configurations where all three Hn belong to the class that enumerated by gn as illustrated in Figure 2. And /n+1 = /n + 6/ngn + 3/nhn + 9/ngn + 6/ngnhn + 2gn is verified by adding these configurations. Similarly, the expressions of gn+1, hn+1 and pn+1 can be obtained with appropriate configurations of its three Hn as illustrated in Figures 3-5. □ Figure 2: Illustration for the expression of /n+i. The multiplication of three on the right-hand-side corresponds to the three possible orientations of Hn+1, the multiplication of two on the right-hand-side corresponds to reflection symmetry with respect to the central vertical axis and the multiplication of six on the right-hand-side corresponds to the six possible of considering both orientations and reflection symmetry. In the following, we will estimate the value ^ = '"HfV the asymptotic growth constant for the Tower of Hanoi graph Hn. The values of fn, g„, hn, pn for small n are listed in Table 1 by Lemma 3.1, and grow exponentially. For the Tower of Hanoi graph Hn, define the ratios _ gn q ___ pn an c , Pn , Yn T in gn hn where n is a positive integer. Their values for small n are listed in Table 2. From the initial values of fn, gn, hn,pn, it is easy to see that fn > gn > hn > pn for all positive integer n by induction. Alternatively, these inequalities can be obtained by an injection. For instance, if one of the independent sets enumerated by gn is given, one can remove H. Chen et al.: Independent sets on the Towers of Hanoi graphs 251 gn+1 + / \x2+/ \x2 +/ \x2 2 2 +/ \ + x2+/ \x2+/ \ + / \x2+/ \x2 2 2 2 Figure 3: Illustration for the expression of gn+1. The multiplication of two on the right-hand-side are corresponds to the reflection symmetry with respect to the central vertical axis. n+1 + / \x2+/ \x2+/ \x2 2 2 - x2V V2V \ + f \x2+/ \x2+/ \x2+/ \x2+/ \x2 Figure 4: Illustration for the expression of hn+1. The multiplication of two on the right-hand-side are corresponds to the reflection symmetry with respect to the central vertical axis. + Figure 5: Illustration for the expression of pn+1. The multiplication of three on the right-hand-side corresponds to the three possible orientations of Hn+1, the multiplication of two on the right-hand-side corresponds to reflection symmetry with respect to the central vertical axis and the multiplication of six on the right-hand-side corresponds to the six possible of considering both orientations and reflection symmetry. Table 1: The first few values of fn, gn, hn,pn and in on Hn. n 0 1 2 3 fn 1 18 38284 342408411795232 gn 1 8 15840 141595222762112 hn 0 3 6546 58553484583728 pn 0 1 2702 24213460330512 in 4 52 108144 967067994163264 the corner vertex to obtain another independent set that are enumerated by fn such that fn > gn is established. Similarly, other two inequalities can be established. It follows that On,^n, Yn € (0, 1). 252 Ars Math. Contemp. 12 (2017) 247-260 Table 2: The first few values of an, An, Yn on Hn n 1 2 3 an 0.444444444444444 0.413749869397137 0.413527290465016 An 0.375 0.413257575757575 0.413527260606109 Yn 0.333333333333333 0.412771157959058 0.413527230747269 Lemma 3.2. For any positive integer n, the ratios satisfy an > An > Yn. When n increases, the ratio an decreases monotonically while Yn increases monotonically. The three ratios in the large n limit are equal to each other lim an = lim An = lim Yn. Proof. By the definition of an, An, Yn, we have _ Bn ^ _ Cn _ Dn an+1 an , Pn+1 an ^ , Yn+1 an An Cn for a positive integer n, where An = 1 + 6an + 3a„^„ + 9a;; + 6a;;^n + Bn = 1 + 2An + AnYn + 4an + 8anAn + 2anAnYn + 2anAn + 3an + 4an A n Cn = 1 + 4An + 2AnYn + 3^n + 2^ Yn + 2an + 7anAn + 2anAnYn + 4anAn, n n nn 3nYn ^n 1 "An in ~ ^^n Dn = 1 + 6An + 3AnYn + 9^n + 6^ Yn + 2^n. n xnAnYn nn n An, In the following, we show that 1 < Yn < An < an < 4 by induction on n. It is true 3 < /n ^ An ^ y-*-n < g 3 < Yn < An < an < g xn An, ^n > An Yn and £n for n = 1,2,3,4 from Table 2. Suppose that 3 < Yn < An < an < 4 for n > 4. Let £n = an - Yn. Then £n > an - An, £n > An - Yn and £n € (0,1). Now, an an+1 an an Bn An an (An - Bn) An = -Tn [(2 + 6an + 4anAn + 2an + An)(an - An) An + (2anAn + An)(An - Yn)] > 0, . an(Bn - AnCn) an+1 - An+1 =-- AnBn > 0, where Bn-AnCn =(10an An + 5an + anAn + 4 an + An + 1)(an - An)2 + (4anAn + 2 an A + 6anAn + 2An)(an - An)(an - Yn) + (4anAn + 10anAn + 2anAn + 2anAn + An)(An - Yn)(an - An) + (2anAn + A"^ )(«n - Yn)(A n Yn) + (4anAn + 2anAn)(An - Yn)2 > 0, 2 H. Chen et al.: Independent sets on the Towers of Hanoi graphs 253 A» B» =10a» + 20» + 23a»0» + 0»7» + 8a»0» + 88a»0» + 133a»0» + 70a»0» + 8a» 0» + 36a» + 56a» + 35«» + 6a» + 48a»0» + 6a20» + 78a» 0» + 12a»0» + 12a»0»7» + 28a»0» + 12a»0»7» + 8a»0»7» + 3a»0»7» + 21a»0»7» + 20a»0»7» + 4a»0»7» + 1 >4a»0» + 8a» 0» + 20a» 0» + 5a» + 8a»0» + 9a» 0» + 4a» + 3a»0» + 2a»0» + a». Then a»+i — 0»+i a»(B» — A»C») A»B» e2 [4a»^» + 8a» ,0» + 20a» 0» + 5a» + 8a»0» + 9a»0» + 4a» + 3a»0» + 2a»0» + a»] a» — 0» and e» >0» — 7 _ _ Similarly, we have 0»+i — y»+i = "n(Cf B> 0, where C» — B»D» =[(100» + 40» 7» + 40» +40» + 1)(a» — 0») + (20» + 90» + 20»)(a» — 7») + (2a»0» + a»0»)(0» — Y»)](a» — 0») + [(4a»0» + 100» )(a» — 0») + (4a» 0» + 20» )(a» — 7») + (2a»0» + 0»)(0» — 7»)](0» — 7») > 0, B»C» =16a»0» + 8a»0» 7» + 40a»0» + 6a»0» 7» + 29a» 0» + 6a» + 8a»0» + 20a»0» 7» + 58a» 0» + 4a»0» 7» + 44a» 0» 7» + 101a»0» + 18a»0»7» 2 24 432 3 3 + 60a»0» + 11a» + 4a»0» 7» + 6a»0» + 4a»0» 7» + 30a»0» 7» + 40a»0» OOOO Q O + 6a»0»Y» + 43a»0»Y» + 64a» 0» + 14a»0»Y» + 35a»0» + 6a» + 20» 7» + 70» 7» + 60» + 20» 7» + 100» 7» + 110» + 30» 7» + 60» + 1. Thus, we have a»(C» — B»D») 0»+i — Y»+i =" e2 0. nHn)\Hn - In) ^ '^Hn /nV^n - Hn) So, we have (i) an-«n+1 > 0, (ii) 0 < an+i-,n+i < ^n, (iii) 0 < ,n+i -Yn+1 < en and (iv) Yn+i - Yn > 0 From (ii) and (iii), we can obtain that en+1 = an+1 - Yn+1 < 2^ < 81 for all positive integer n by induction. It follows that for any positive integer m < n, en < 2en_1 < 2[2en-2]2 < ■ ■ ■ < . Since em G (0,1) for any positive integer m, we have that the values of an, ,n, Yn are close to each other when n becomes large. □ Numerically, we can find lim an = lim ,n = lim Yn = 0.4135272769487595999 ■ ■ ■ n^w n^w n^w From the lemmas above, we get the bounds for the number of independent sets. Theorem 3.3. For any positive integer m < n, on—m , , 3(3n m — 1) 0 on—m , , 3(3n m — 1) /m (1 + 2Ym)-2-(1+ Yn)3 < in < (1 + 2am)-2-(1 + an) Proof. By Lemmas 3.1 and 3.2 and the definition of an, ,n, Yn, we have /n =/3-1(1 + 6an-1 + 3an-1,n-1 + 9an- + 6an_1,n-1 + 2an_1) ln fm v(Hn) 2 x 3m So, the bounds for p = ^Hy follow. m ln(1 + 27m) ln(1 + 27m) ln(1 + 7n) +--^—^---^—^--1--^- 2 3n □ As m increases, the difference between the upper and lower bounder in Theorem 3.4 becomes small and the convergence is rapid. Numerically, the asymptotic growth constant for the number of independent sets of the Tower of Hanoi graph Hn in the large n limit is p = 0.42433435855938823 • • • .In fact, the numerical value of p can be obtained with more than a hundred significant figures accurate when m is equal to seven. 4 The number of independent sets on graphs Sk,n The Sierpiriski graphs Sk,n were introduced by Klavzar and Milutinovic in 1997 in [25]. The graph Sfcj0 is simply the complete graph on k vertices, Sk,n is constructed from Skn-1 by copying k times Skn-1 and adding exactly one edge between each pair of copies. For the construction, one can easily derive that the total number of vertices and edges in Sk n are v(Sk,n) = kn+1 and e(Sk,n) = 1 (kn+2 - k), respectively. In particularly, we can see those graphs are exactly the graphs of the Tower of Hanoi problem for k = 3 and another case as shown in Figure 6 for k = 4. S41 S4,n-1 S4,n-1 S4,n-1 S4,n-1 Figure 6: The graphs S4,0, S4j1, S4,2 and the construction of S4,n. The method given in the previous section can be applied to enumeration the number of independent sets on this Sierpiriski graphs with k > 4, but the items of the recursion relations will become larger and larger with the increase of k. To seek the number of independent sets on S4 n, we use the following definitions: (i) Define f4,n as the number of independent sets such that all four outmost vertices are not in the vertex sets. (ii) Define g4 n as the number of independent sets such that only one certain outmost vertex are in the vertex sets. (iii) Define h4 n as the number of independent sets such that exactly two certain outmost vertex are in the vertex sets. (iv) Define p4,n as the number of independent sets such that exactly three certain outmost vertex are in the vertex sets. (v) Define q4,n as the number of independent sets such that all four outmost vertex are in the vertex sets. 256 Ars Math. Contemp. 12 (2017) 383-413 Table 3: The first few values of /4,n, g4,n, h4,n, p4,n, q4,n and ¿4,n on n 1 2 3 /4 n 163 13064274739 497661511371512614009322138806617451967507 <74. n 52 3951119257 150487045809089786329485928937399858428184 h-4. n 15 1194624638 45505530112368879421817904248654649805971 P4. n 4 361093492 13760342318790991781550553074012255470504 94. n 1 109115158 4160967243331065589513567798163834387921 ¿4. n 478 37589988721 1431845211800580068573889060142357640786006 Table 4: The first few values of a4,n, ^4,n, Y4,n ; and J4,n on S4,n. n 1 2 3 «4,n Y4,n &4,n 0.319018404907975 0.288461538461538 0.266666666666666 0.25 0.302436938592921 0.302350944199809 0.302265230863252 0.302179796693760 0.302388355077651 0.302388354211550 0.302388353345449 0.302388352479348 The quantities /4,n, g4,n, h4,n, p4,n, q4,n of S4,n are lengthy and given in the appendix. Some values of /4,n, g4,n, h4,n, p4,n, q4,n, ¿4,n are listed in Table 3. These numbers grow exponentially, and have no integer factorizations. There are four equivalent g4,n, six equivalent h4,n, and four equivalent pn. By definition, we have ¿4,n = /4,n + 4g4,n + 6fr-4,n + 4p4,„ + q4,„. The initial values at stage zero are /4,o = g4,o = 1, h4,o = p4,o = q4,o = 0 and ¿4,o = 5. Define ratios «4,n = g4,n//4,n, &,n = h4,„/g4,„,Y4,„ = P4,n/h4,n, ¿4,n = 94,n/P4,n. As n increases, we find a4,n decrease monotonically while ^4,„, Y4,n and J4,n increase monotonically with the relation a4,n > ^4,„ > Y4,n > J4,n. The values of these ratios for small n are listed in Table 4. Numerically, we can find lim a4 n = lim n = lim y4 n = lim J4 n = 0.30238835458805297767 • • • By a similar argument as the Tower of Hanoi graph Hn in the last section, the asymptotic growth constant for the number of independent sets on S4 ,n is bounded by ln /4 , m + ln(1 + 2^4 , m) ln /4 , m + ln(1 + 2a , m) 4m+1 + 2 X 4m — — 4m+1 + 2 X 4m where = limV(S4n)^w V^'") and m is a positive integer. Then, we can obtain the asymptotic growth constant for the number of independent sets on the Sierpinsk graph S4,n in the large n limit is ^ = 0.378737140730676994823835 • • • . We can also continue verify a similarly bound for the asymptotic growth constant on S5 n, in order to avoid verbosity, we are not to describe here. However, the recursion relations of the number of independent sets for general k are difficult to obtain. From what has been discussed above, we have the following conjecture for the Sierpiriski graphs Sk n with positive integers k and m. H. Chen et al.: Independent sets on the Towers of Hanoi graphs 257 Conjecture 4.1. The asymptotic growth constant for the number of independent sets on the Sierpinsk graph S4,n is bounded by ln fk ln(1 + 2^k fa „ ln fk ln(1 + 2ak ,m J km+i + 2 x km " Mk - km+1 + 2 x km where the ratios are defined as ak,n = gk,n/fk,n, ^k,n = wk,n/yk,n, fk,n is the number of independent sets such that all k outmost vertices are not in the vertex subset, gk,n is the number of independent sets such that one certain outmost vertex is in the vertex subset, yk,n is number of independent sets such that all but one certain outmost vertex are in the vertex subset, and wk,n is the number of independent sets such that all k outmost vertices are in the vertex subset. Appendix: Recursion relation for S4,n We give the recursive relation for the Siepinski graph S4n here. Since the subscript is k = 4 for all the quantities throughout this section, we will use the simplified notation fn+i to denote f4,n+i and similar notations for other quantities. For any non-negative integer n, we have fn+i = f4 + 12f3gn + 12f3hn + 48^2 + 4fan + 84fanK + 72fng3n + 24fanPn + fun + 156fng2n hn + 30g4n + 12fanPn + 36fng2nPn + 84fngnh2n + 60g3n hn + 24fngnhnPn + 8g^Pn + 8^2 + 24g1 h2n, gn+i = fan + 3f3hn + 9f^ + 3 fan + 33fanK + 24^ + fan + 24fanPn + 21 fn h'n + 96 fn g2n hn + 18 gn + 6fanqn + 21fanPn + 51fn g2n Pn + 93fngnh2n + 69g3n hn + 3f2 hn qn + 9fngn qn + 3 fan + 66fngn hnPn + 24g^n + 21 fn^ + 66g1 hn +6fngn hn qn + 2gn qn + 6fn gnP2n + 12 fn h2nPn + 24g2 hnPn + 14gnhn, hn+i = fan +6fanhn + 6fng2 +6fanPn + 8fa2n + 38fng1 hn +8g2 + 2fanqn + 14 fn hnPn + 30fngl,Pn + 64fngnh2n + 50g2 hn + 4f2 hnqn + 8fngi qn + 5fal, + 80fngnhnPn + ^idg^n + 26 fn^ + 87 gl h2n + 2fajnqn + 16fngnhn qn + 6g2^i qn + 18fngnP2n + 34fnh2nPn + 72g2 hnPn + 44gnh3n + 4fngnPnqn + 4fnh2l,qn, + 8g1 hnqn + 8 fn hnP2n + 8^ + 28gn h^n + 4h4n, Pn+i = fngn + 9fng2nhn + 3g2 + + 24fngnh2n + 27 g3n hn + 3fnglqn + 42fngnhnPn + 22g3rlPn + 18fnhn + 75g2 hn + 12fngnhnqn + 6g2 qn + 15 fngnPri + 39fnh2nPn + 99gnhnPn + 69 g + 6fngnPn qn + 9fnh2nqn + 21g2nhnqn + 21fnhnP2n + 24g2 P2n + 96gn h2n Pn + 15h2 +6fn hnPn qn + 6g2 Pnqn + 12gn hi qn + 2fnPn + 24gn hnP2n + 14h3nPn, qn+i = g2 + 12gihn + 12glPn+48g2 h2+4g^qn+84g2 hnPn+72gnhn+24g2 hnqn + 30 g2 p1 + 156gnh2nPn + 30h4n + 12g2nPnqn + 36gnh2nqn + 84gnhnP2n + 6(0^^2 + 24gnhnPnqn + 8hnqn + 8gnPn + 24h2ni)2n. There are always 729 = 36 terms in these equations. 258 Ars Math. Contemp. 12 (2017) 383-413 Acknowledgments The authors are thankful to the anonymous referees for their useful comments. References [1] R. Baxter, I. Enting and S. Tsang, Hard-square lattice gas, J. Stat. Phys. 22 (1980), 465-489. [2] B. Bollobas and B. D. McKay, The number of matchings in random regular graphs and bipartite graphs, J. Combin. Theory Ser. B 41 (1986), 80-91, doi:10.1016/0095-8956(86)90029-8, http://dx.doi.org/10.1016/00 95-8 956(86)9002 9-8. [3] G. R. Brightwell, O. Haggstrom and P. Winkler, Nonmonotonic behavior in hard-core and widom-rowlinson models, J. Stat. Phys. 94 (1999), 415-435. [4] N. J. Calkin and H. S. Wilf, The number of independent sets in a grid graph, SIAM J. Discrete Math. 11 (1998), 54-60 (electronic), doi:10.1137/S089548019528993X, http://dx.doi. org/10.1137/S089548019528993X. [5] T.-H. Chan, A statistical analysis of the Towers of Hanoi problem, Int. J. Comput. Math. 28 (1989), 57-65, doi:10.1080/00207168908803728. [6] S.-C. Chang, L.-C. Chen and W. Yan, Asymptotic enumeration of independent sets on the Sierpinski gasket, Filomat 27 (2013), 23-40, doi:10.2298/FIL1301023C, http://dx.doi. org/10.2298/FIL1301023C. [7] H. Chen, R. Wu, G. Huang and H. Deng, Dimer-monomer model on the Towers of Hanoi graphs, Internat. J. Modern Phys. B 29 (2015), 1550173, 13, doi:10.1142/ S0217979215501738, http://dx.doi.org/10.1142/S021797 9215501738. [8] P. Cull and I. Nelson, Error-correcting codes on the Towers of Hanoi graphs, Discrete Math. 208/209 (1999), 157-175, doi:10.1016/S0012-365X(99)00070-9, combinatorics (Assisi, 1996), http://dx.doi.org/10.1016/S0012-365X(99)00070-9. [9] K. Engel, On the Fibonacci number of an m x n lattice, Fibonacci Quart. 28 (1990), 72-78. [10] E. J. Farrell, Counting matchings in graphs, J. Franklin Inst. 324 (1987), 331-339, doi: 10.1016/0016-0032(87)90046-9, http://dx.doi.org/10.1016/0016-0032(87) 90046-9. [11] E. J. Farrell, Matchings in rectangular cacti, J. Math. Sci. (Calcutta) 9 (1998), 163-183. [12] R. Grigorchuk and Z. Sunik, Asymptotic aspects of Schreier graphs and Hanoi Towers groups, C. R. Math. Acad. Sci. Paris 342 (2006), 545-550, doi:10.1016/j.crma.2006.02.001, http: //dx.doi.org/10.1016/j.crma.2006.02.001. [13] W. Guo and H. W. Blote, Finite-size analysis of the hard-square lattice gas, Physical Review E 66 (2002), 046140. [14] I. Gutman and F. Harary, Generalizations of the matching polynomial, Utilitas Math. 24 (1983), 97-106. [15] O. Haggstrom, Ergodicity of the hard-core model on Z2 with parity-dependent activities, Ark. Mat. 35 (1997), 171-184, doi:10.1007/BF02559597, http://dx.doi.org/10.10 07/ BF02 55 95 9 7. [16] J. R. Heringa, H. W. J. Blote and E. Luijten, High-dimensional lattice gases, J. Phys. A 33 (2000), 2929-2941, doi:10.1088/0305-4470/33/15/302, http://dx.doi.org/10. 1088/0305-4470/33/15/302. [17] A. M. Hinz, The Tower of Hanoi, Enseign. Math. (2) 35 (1989), 289-321. H. Chen et al.: Independent sets on the Towers of Hanoi graphs 259 [18] A. M. Hinz, Pascal's triangle and the Tower of Hanoi, Amer. Math. Monthly 99 (1992), 538544, doi:10.2307/2324061, http://dx.doi.org/10.230 7/23240 61. [19] A. M. Hinz, Shortest paths between regular states of the Tower of Hanoi, Inform. Sci. 63 (1992), 173-181, doi:10.1016/0020-0255(92)90067-I, http://dx.doi.org/10.1016/ 0020-0255(92)90067-1. [20] A. M. Hinz, S. KlavZar, U. MilutinoviC, D. Parisse and C. Petr, Metric properties of the Tower of Hanoi graphs and Stern's diatomic sequence, European J. Combin. 26 (2005), 693-708, doi: 10.1016/j.ejc.2004.04.009, http://dx.doi.org/10.1016/j.ejc.2004.04.009. [21] A. M. Hinz, S. KlavZar, U. Milutinovic and C. Petr, The tower of Hanoi—myths and maths, Birkhauser/Springer Basel AG, Basel, 2013, doi:10.1007/978-3-0348-0237-6, with a foreword by Ian Stewart, http://dx.doi.org/10.10 07/97 8-3-0 34 8-0237-6. [22] A. M. Hinz and D. Parisse, On the planarity of Hanoi graphs, Expo. Math. 20 (2002), 263-268, doi:10.1016/S0723-0869(02)80023-8, http://dx.doi.org/10. 1016/S0723-0869(02)80023-8. [23] H. Hosoya, Topological index. a newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bull. Chem. Soc. Jpn. 44 (1971), 2332-2339. [24] J. Kahn, An entropy approach to the hard-core model on bipartite graphs, Combin. Probab. Comput. 10 (2001), 219-237, doi:10.1017/S0963548301004631, http://dx.doi.org/ 10.1017/S0963548301004631. [25] S. Klavzar and U. Milutinovic, Graphs S(n, k) and a variant of the Tower of Hanoi problem, Czechoslovak Math. J. 47(122) (1997), 95-104, doi:10.1023/A:1022444205860, http:// dx.doi.org/10.1023/A:1022444205860. [26] M. Klazar, Twelve countings with rooted plane trees, European J. Combin. 18 (1997), 195-210, doi:10.1006/eujc.1995.0095, http://dx.doi.org/10.100 6/eujc.1995.00 95. [27] H.-F. Law, On the number of independent sets in a tree, Electron. J. Combin. 17 (2010), Note 18, 5, http://www.combinatorics.org/Volume_17/Abstracts/v17i1n18. html. [28] C.-K. Li and I. Nelson, Perfect codes on the Towers of Hanoi graph, Bull. Austral. Math. Soc. 57 (1998), 367-376, doi:10.1017/S0004972700031774, http://dx.doi.org/10. 1017/S0004972700031774. [29] V. Linek, Bipartite graphs can have any number of independent sets, Discrete Math. 76 (1989), 131-136, doi:10.1016/0012-365X(89)90306-3, http://dx.doi.org/10. 1016/0012-365X(89)9030 6-3. [30] R. E. Merrifield and H. E. Simmons, Topological methods in chemistry, Wiley New York etc., 1989. [31] D. Romik, Shortest paths in the Tower of Hanoi graph and finite automata, SIAM J. Discrete Math. 20 (2006), 610-622 (electronic), doi:10.1137/050628660, http://dx.doi.org/ 10.1137/050628660. [32] D. H. Rouvray, The role of graph-theoretical invariants in chemistry, in: Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986), volume 55, 1986 pp. 253-265. [33] L. K. Runnels, Phase transitions of hard sphere lattice gases, Comm. Math. Phys. 40 (1975), 37-48. [34] A. D. Scott and A. D. Sokal, The repulsive lattice gas, the independent-set polynomial, and the Lovasz local lemma, J. Stat. Phys. 118 (2005), 1151-1261, doi:10.1007/s10955-004-2055-4, http://dx.doi.org/10.1007/s10 955-004-2055-4. 260 Ars Math. Contemp. 12 (2017) 383-413 [35] E. Teufl and S. Wagner, Enumeration problems for classes of self-similar graphs, J. Combin. Theory Ser. A 114 (2007), 1254-1277, doi:10.1016/j.jcta.2007.01.007, http://dx.doi. org/10.1016/j.jcta.20 07.01.0 07. [36] E. Teufl and S. Wagner, Exact and asymptotic enumeration of perfect matchings in self-similar graphs, Discrete Math. 309 (2009), 6612-6625, doi:10.1016/j.disc.2009.07.009, http:// dx.doi.org/10.1016/j.disc.2009.07.00 9. [37] E. Teufl and S. Wagner, Resistance scaling and the number of spanning trees in self-similar lattices, J. Stat. Phys. 142 (2011), 879-897, doi:10.1007/s10955-011-0140-z, http://dx. doi.org/10.1007/s10 955-011-0140-z. [38] N. Trinajstic, Chemical graph theory, Mathematical Chemistry Series, CRC Press, Boca Raton, FL, 2nd edition, 1992, doi:10.1007/s10910-008-9464-6, http://dx.doi.org/10. 1007/s10910-008-9464-6. [39] J. van den Berg and J. E. Steif, Percolation and the hard-core lattice gas model, Stochastic Process. Appl. 49 (1994), 179-197, doi:10.1016/0304-4149(94)90132-5, http://dx.doi. org/10.1016/0304-4149(94)90132-5. [40] K. Weber, On the number of stable sets in an m x n lattice, Rostock. Math. Kolloq. (1988), 28-36. [41] Y. Zhao, The number of independent sets in a regular graph, Combin. Probab. Comput. 19 (2010), 315-320, doi:10.1017/S0963548309990538, http://dx.doi.org/10.1017/ S0 96354 830 99 90538.