Enumeration problems for classes of self-similar graphs
Enumeration problems for classes of self-similar graphs
复制标题
DOI：
10.1016/j.jcta.2007.01.007
复制
发表时间：
2007-10
期刊：
影响因子：
--
通讯作者：
Elmar Teufl;S. Wagner
中科院分区：
文献类型：
--
作者：
Elmar Teufl;S. Wagner
我们描述了一类自相似图的一般构造原理。对于各种枚举问题，我们表明，这种结构导致多项式系统的递归，并提供方法来解决这些递归渐近。这是示出了不同的例子，涉及经典的自相似图，如Sierpienski图。我们研究的计数问题包括计数独立子集，匹配和连通子集。
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.