×

Copy-paste trees and their growth rates. (English) Zbl 1345.05014

Summary: In this paper, we describe a copy-and-paste method for constructing a class of infinite self-similar trees. A copy-paste tree is constructed by repeatedly attaching copies of a finite tree (called a generator) to certain designated attachment vertices. We show that each generator has an associated nonnegative matrix which can be used to determine a formula for the growth function of the copy-paste tree. In our main theorem, we use results from Perron-Frobenius theory to show that every copy-paste tree has exponential growth, with growth rate equal to the spectral radius of its associated matrix.

MSC:

05C05 Trees
05C10 Planar graphs; geometric and topological aspects of graph theory
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: DOI Euclid

References:

[1] W. Ballmann, Lectures on spaces of nonpositive curvature , Birkhauser, Basel, 1995. · Zbl 0834.53003
[2] A. Berman and R.J. Plemmons, Nonnegative matrices in the mathematical sciences , Academic Press, New York, 1979. Reprinted by SIAM, Philadelphia, 1994. · Zbl 0484.15016
[3] D. D’Angeli, Horofunctions on Sierpinski type triangles , Util. Math. (2014).
[4] M. Keller, D. Lenz and S. Warzel, An invitation to trees of finite cone type : Random and deterministic operators , http://arxiv.org/pdf/1403.4426.pdf. · Zbl 1277.82030
[5] R. Lyons, Random walks and percolation on trees , Ann. Probab. 18 (1990), 931-958 · Zbl 0714.60089
[6] H. Minc, Nonnegative matrices , John Wiley and Sons, New York, 1988. · Zbl 0638.15008
[7] J. Previte, Graph substitutions , Ergod. Th. Dyn. Syst. 18 (1998), 661-686. · Zbl 0985.37028
[8] M. Previte, J. Previte, and M. Vanderschoot, Limits of vertex replacement rules , Rocky Mountain J. Math. 37 , (2007), 1001-1026. · Zbl 1211.28009
[9] S. Sternberg, Dynamical systems , Dover Publications, Mineola, New York, 2010. · Zbl 1215.37002
[10] E. Teufl and S. Wagner, Enumeration problems for classes of self-similar graphs , J. Combin. Th. 114 , (2007), 1254-1277. · Zbl 1124.05046
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.