图的完全积的独立数和独立多项式

作     者：杨利民 Yang Limin

作者机构：大理大学数学与计算机学院云南大理671003 

出 版 物：《大理大学学报》 (Journal of Dali University)

年 卷 期：2023年第8卷第6期

页      面：1-8页

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：国家自然科学基金项目(11861005) 大理大学高层次人才科研启动基金项目(KY0719203410) 

主　　题：稳定集合 独立数 完全积 独立多项式 单峰性 

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