科研之友
微信
新浪微博
Facebook
分享链接
摘要
在图论中，独立数和独立多项式是NP难问题。它们是非常困难的问题，然而，通过变换问题，可以找到一种求解独立数和独立多项式的有效方法。通过将基数k的稳定集合问题转化为k阶完全子图问题，得到独立多项式的计算方法。类比，将最大稳定集合的大小转化为最大完全图的大小，得到独立数的计算方法。利用组合计算给出许多图的完全积的独立数和独立多项式的显式公式。进一步利用发生函数导出图的Merrifield-Simmons指数。证明了一些独立多项式的系数序列是单峰的，有一些不是单峰的，并否定了树的独立多项式的系数序列是单峰的猜想，这对组合数学和图论有重要的价值和意义。
- 出版日期2023
