论文标题
在Riordan图中计算独立集
Counting independent sets in Riordan graphs
论文作者
论文摘要
Riordan图的概念最近引入了，它是众所周知的Pascal图和Toeplitz图的深远概括。但是，除了特定的toeplitz图子类外，Riordan图中的独立集中尚无任何人知道。 在本文中，我们为各类Riordan图的独立集数量提供了精确的枚举和下限和上限。值得注意的是，我们提供了各种方法来解决从结构分解定理到单词组合学方法的问题。我们的某些结果对于任何图表都是有效的。
The notion of a Riordan graph was introduced recently, and it is a far-reaching generalization of the well-known Pascal graphs and Toeplitz graphs. However, apart from a certain subclass of Toeplitz graphs, nothing was known on independent sets in Riordan graphs. In this paper, we give exact enumeration and lower and upper bounds for the number of independent sets for various classes of Riordan graphs. Remarkably, we offer a variety of methods to solve the problems that range from the structural decomposition theorem to methods in combinatorics on words. Some of our results are valid for any graph.
