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

Independent Number and Independent Polynomial of Complete Product of Graph

作　　者：杨利民 Yang Limin(College of Mathematics and Computer,Dali University,Dali,Yunnan 671003,China)

机构地区：[1]大理大学数学与计算机学院,云南大理671003

出　　处：《大理大学学报》2023年第6期1-8,共8页Journal of Dali University

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

摘　　要：在图论中,独立数和独立多项式是NP难问题。它们是非常困难的问题,然而,通过变换问题,可以找到一种求解独立数和独立多项式的有效方法。通过将基数k的稳定集合问题转化为k阶完全子图问题,得到独立多项式的计算方法。类比,将最大稳定集合的大小转化为最大完全图的大小,得到独立数的计算方法。利用组合计算给出许多图的完全积的独立数和独立多项式的显式公式。进一步利用发生函数导出图的Merrifield-Simmons指数。证明了一些独立多项式的系数序列是单峰的,有一些不是单峰的,并否定了树的独立多项式的系数序列是单峰的猜想,这对组合数学和图论有重要的价值和意义。In graph theory,independent number and independent polynomial are NP-hard problems.They are very difficult problems,however,by transforming the problem,an effective method to solve independent number and independent polynomial can be found.By transforming the stable set problem of radix k into a k-order complete subgraph problem,the calculation method of independent polynomial is obtained.Anology,by transforming the size of the maximum stable set into the size of the maximum complete graph,the calculation method of the independent number is obtained.Using combinatorial calculations,explicit formulas for the independent number and independent polynomial of many graph's complete product are given.Furthermore,using the generating function,the Merrifield-Simmons index of the graph is derived.It is proved that some coefficient sequences of independent polynomials are unimodal and some are not,and the conjecture that the coefficient sequences of the independent polynomial of trees are unimodal is denied,which is of great value and significance to combinatorial mathematics and graph theory.

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

分 类 号：O157.1[理学—数学] O157.5[理学—基础数学]