Enumeration problems for classes of self-similar graphs. (English) Zbl 1124.05046
Summary: We describe a general construction principle for a class of self-similar graphs. For various enumeration problems, we show that this construction leads to polynomial systems of recurrences and provide methods to solve these recurrences asymptotically. This is shown for different examples involving classical self-similar graphs such as the Sierpiński graphs. The enumeration problems we investigate include counting independent subsets, matchings and connected subsets.
MSC:
| 05C30 | Enumeration in graph theory |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
Software:
OEISOnline Encyclopedia of Integer Sequences:
a(0) = 0; for n > 0, a(n) = (a(n-1) + 1)^2.a(n) = n(a(n-1) + 1), a(0) = 0.
References:
| [1] | Aho, A. V.; Sloane, N. J.A., Some doubly exponential sequences, Fibonacci Quart., 11, 4, 429-437 (1973) · Zbl 0277.10011 |
| [2] | Alexander, S.; Orbach, R., Density of states on fractals: Fractons, J. Phys. Lett., 43, L625-L631 (1982) |
| [3] | Barlow, M. T., Diffusions on fractals, (Lectures on Probability Theory and Statistics. Lectures on Probability Theory and Statistics, Saint-Flour, 1995 (1998), Springer-Verlag: Springer-Verlag Berlin), 1-121 · Zbl 0916.60069 |
| [4] | Bartholdi, L.; Grigorchuk, R. I., On the spectrum of Hecke type operators related to some fractal groups, Tr. Mat. Inst. Steklova, 231, 5-45 (2000) · Zbl 1172.37305 |
| [5] | Baxter, R. J.; Enting, I. G.; Tsang, S. K., Hard-square lattice gas, J. Statist. Phys., 22, 4, 465-489 (1980) |
| [6] | Bollobás, B.; McKay, B. D., The number of matchings in random regular graphs and bipartite graphs, J. Combin. Theory Ser. B, 41, 1, 80-91 (1986) · Zbl 0602.05050 |
| [7] | Calkin, N. J.; Wilf, H. S., The number of independent sets in a grid graph, SIAM J. Discrete Math., 11, 1, 54-60 (1998), (electronic) · Zbl 0910.05007 |
| [8] | Engel, K., On the Fibonacci number of an \(m \times n\) lattice, Fibonacci Quart., 28, 1, 72-78 (1990) · Zbl 0686.05027 |
| [9] | Fabrykowski, J.; Gupta, N., On groups with sub-exponential growth functions. II, J. Indian Math. Soc. (N.S.), 56, 1-4, 217-228 (1991) · Zbl 0868.20029 |
| [10] | Farrell, E. J., Counting matchings in graphs, J. Franklin Inst., 324, 3, 331-339 (1987) · Zbl 0625.05040 |
| [11] | Farrell, E. J., Matchings in rectangular cacti, J. Math. Sci. (Calcutta), 9, 2, 163-183 (1998) |
| [12] | (Grabner, P.; Woess, W., Fractals in Graz 2001, Analysis—Dynamics—Geometry—Stochastics. Fractals in Graz 2001, Analysis—Dynamics—Geometry—Stochastics, Trends Math. (2003), Birkhäuser: Birkhäuser Basel) · Zbl 1005.00032 |
| [13] | Hosoya, H., Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bull. Chem. Soc. Jpn., 44, 2332-2339 (1971) |
| [14] | Ionascu, E.; Stanica, P., Effective asymptotics for some nonlinear recurrences and almost doubly-exponential sequences, Acta Math. Univ. Comenian. (N.S.), 73, 1, 75-87 (2004) · Zbl 1109.11013 |
| [15] | Kigami, J., Analysis on Fractals, Cambridge Tracts in Math., vol. 143 (2001), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0998.28004 |
| [16] | Kirschenhofer, P.; Prodinger, H.; Tichy, R. F., Fibonacci numbers of graphs. II, Fibonacci Quart., 21, 3, 219-229 (1983) · Zbl 0498.05039 |
| [17] | Kirschenhofer, P.; Prodinger, H.; Tichy, R. F., Fibonacci numbers of graphs. III. Planted plane trees, (Fibonacci Numbers and Their Applications. Fibonacci Numbers and Their Applications, Patras, 1984. Fibonacci Numbers and Their Applications. Fibonacci Numbers and Their Applications, Patras, 1984, Math. Appl., vol. 28 (1986), Reidel: Reidel Dordrecht), 105-120 · Zbl 0597.05034 |
| [18] | Klazar, M., Twelve countings with rooted plane trees, European J. Combin., 18, 2, 195-210 (1997) · Zbl 0868.05017 |
| [19] | Knuth, D. E., The Art of Computer Programming, vol. 1: Fundamental Algorithms, Addison-Wesley Series in Computer Science and Information Processing (1975), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0191.17903 |
| [20] | Krön, B., Green functions on self-similar graphs and bounds for the spectrum of the Laplacian, Ann. Inst. Fourier (Grenoble), 52, 6, 1875-1900 (2002) · Zbl 1012.60063 |
| [21] | Krön, B., Growth of self-similar graphs, J. Graph Theory, 45, 3, 224-239 (2004) · Zbl 1033.05090 |
| [22] | Krön, B.; Teufl, E., Asymptotics of the transition probabilities of the simple random walk on self-similar graphs, Trans. Amer. Math. Soc., 356, 1, 393-414 (2004), (electronic) · Zbl 1030.60064 |
| [23] | Lewin, L., Polylogarithms and Associated Functions (1981), North-Holland Publishing Co.: North-Holland Publishing Co. New York · Zbl 0465.33001 |
| [24] | Malozemov, L.; Teplyaev, A., Pure point spectrum of the Laplacians on fractal graphs, J. Funct. Anal., 129, 2, 390-405 (1995) · Zbl 0822.05045 |
| [25] | Meir, A.; Moon, J. W., On subtrees of certain families of rooted trees, Ars Combin., 16, B, 305-318 (1983) · Zbl 0535.05024 |
| [26] | Meir, A.; Moon, J. W., On maximal independent sets of nodes in trees, J. Graph Theory, 12, 2, 265-283 (1988) · Zbl 0655.05039 |
| [27] | Merrifield, R. E.; Simmons, H. E., Topological Methods in Chemistry (1989), Wiley: Wiley New York |
| [28] | Nagnibeda, T.; Woess, W., Random walks on trees with finitely many cone types, J. Theoret. Probab., 15, 2, 383-422 (2002) · Zbl 1008.60061 |
| [29] | Prodinger, H.; Tichy, R. F., Fibonacci numbers of graphs, Fibonacci Quart., 20, 1, 16-21 (1982) · Zbl 0475.05046 |
| [30] | Rammal, R., Random walk statistics on fractal structures, J. Statist. Phys., 36, 5-6, 547-560 (1984) · Zbl 0587.60061 |
| [31] | Rammal, R.; Toulouse, G., Random walks on fractal structures and percolation clusters, J. Phys. Lett., 44, L13-L22 (1983) |
| [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, FL, 1986, vol. 55, 1986; 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, FL, 1986, vol. 55, 1986 · Zbl 0628.05060 |
| [33] | Ruskey, F., Listing and counting subtrees of a tree, SIAM J. Comput., 10, 1, 141-150 (1981) · Zbl 0454.68081 |
| [34] | Sabot, C., Spectral properties of self-similar lattices and iteration of rational maps, Mém. Soc. Math. Fr. (N.S.), 92, vi+104 (2003) · Zbl 1036.82013 |
| [35] | Sierpiński, W., Sur une courbe dont tout point est un point de ramification, C. R. Acad. Sci. Paris, 160, 302-305 (1915) · JFM 45.0628.02 |
| [36] | Sloane, N. J.A., The on-line encyclopedia of integer sequences, published electronically at · Zbl 1274.11001 |
| [37] | Székely, L. A.; Wang, H., On subtrees of trees, Adv. in Appl. Math., 34, 1, 138-155 (2005) · Zbl 1153.05019 |
| [38] | Trinajstić, N., Chemical Graph Theory, Mathematical Chemistry Series (1992), CRC Press: CRC Press Boca Raton, FL |
| [39] | Weber, K., On the number of stable sets in an \(m \times n\) lattice, Rostock. Math. Kolloq., 34, 28-36 (1988) · Zbl 0649.05009 |
| [40] | Woess, W., Random Walks on Infinite Graphs and Groups, Cambridge Tracts in Math., vol. 138 (2000), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0951.60002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
