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

摘要：

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

关键词：稳定集合、独立数、完全积、独立多项式、单峰性

所属期刊栏目：8

分类号：O157.1;O157.5(代数、数论、组合理论)

资助基金：国家自然科学基金;大理大学高层次人才科研启动基金项目

在线出版日期：2023-07-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：1-8