کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419522 | 683829 | 2010 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Enumeration of matchings in families of self-similar graphs Enumeration of matchings in families of self-similar graphs](/preview/png/419522.png)
The number of matchings of a graph GG is an important graph parameter in various contexts, notably in statistical physics (dimer–monomer model). Following recent research on graph parameters of this type in connection with self-similar, fractal-like graphs, we study the asymptotic behavior of the number of matchings in families of self-similar graphs that are constructed by a very general replacement procedure. Under certain conditions on the geometry of the graphs, we are able to prove that the number of matchings generally follows a doubly exponential growth. The proof depends on an independence theorem for the number of matchings that has been used earlier to treat the special case of Sierpiński graphs. We also further extend the technique to the matching-generating polynomial (equivalent to the partition function for the dimer–monomer model) and provide a variety of examples.
Journal: Discrete Applied Mathematics - Volume 158, Issue 14, 28 July 2010, Pages 1524–1535