论文研究 几乎所有树木都没有完美的支配集吗?

如果S是G的一组顶点,并且对于G的每个顶点v,或者v在S中且v不与S中的其他顶点相邻,或者v在S中不相邻,则称图形G具有理想的控制集S。 S,但恰好与S的一个顶点相邻。图G可能没有一个,也可能没有一个或多个完美的支配集。 确定图是否具有理想控制集的问题是NP完全的。 计算具有理想支配集的任意图的概率的问题似乎也很困难。 在1994年,Yue [1]推测几乎所有图都没有完美的控制集。 在本文中,通过引入多个相互关联的生成函数并使用组合计算技术,我们计算出最多n个500的n个所有n阶树(有根和无根)中的完美控制集的数量。每棵树(有根和无根)的n个数(最多500个)的阶数为n。我们的计算结果表明,当