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

摘要/Abstract

摘要：

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

关键词:

"> ">稳定集合； ">独立数； ">完全积； ">独立多项式； ">单峰性

Abstract:

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.

Key words:

"> stable set">； independent number">； complete product">； independent polynomial">； unimodality

中图分类号:

杨利民.

图的完全积的独立数和独立多项式 [J]. 大理大学学报, 2023, 8(6): 1-8.

Yang Limin.

Independent Number and Independent Polynomial of Complete Product of Graph [J]. Journal of Dali University, 2023, 8(6): 1-8.

参考文献

〔1〕 BROWN J I，CAMERON B. On the Unimodality of Independence Polynomials of Very Well-Covered Graphs〔J〕. Discrete Mathematics，2018，341（4）： 1138-1143.

〔2〕 LEVIT V E， MANDRESCU E. On Unimodality of Independence Polynomials of Ｓome Well-Covered Trees〔C〕//International Conference on Discrete Mathematics and Theoretical Computer Science. 2003：237-256.

〔3〕 SONG L Z，STATON W，WEI B. Independence Polyno-mials of k-Tree Related Graphs〔J〕. Discrete Applied Mathematics，2010，158（8）：943-950.

〔4〕 MERRIFIELD R H， SIMMONS H E. Topological Methods in Chemistry〔M〕. New York：Wiley， 1989.

〔5〕 XU K X. On the Hosoya Index and the Merrifield-Simmons Index of Graphs with a Given Clique Number〔J〕. Appied Mathematics Letters， 2010， 23： 395-398.

〔6〕 LEVIT V E， MANDRESCU E. Independence Polynomials of Well-Covered Graphs： Generic Counterexamples for the Unimodality Conjecture〔J〕. European Journal of Combina-torics，2006，27（6）： 931-939.

〔7〕 CORNELIS H， LI X L. Clique Polynomials and Independent Set Polynomials of Graphs〔J〕. Discrete Mathematics， 1994， 125（1-3）： 219-228.

〔8〕 WANG T M， YANG L M. Enumeration of Ideal Subgraphs〔M〕. Philadelphia： SIAM， 1991.

〔9〕 COMTET L. Advanced Combinatorics〔M〕. Spriger： D. Reidel Publishing Company， 1974.

〔10〕 BONDY J A， MURTY U S R. Graph Theory with Applications〔M〕. Oxford： The Macmil Press， 1976.

〔11〕王天明. 近代组合学〔M〕. 大连：大连理工大学出版社， 2008.

〔12〕 RICHARD P S. Enumerative Combinatorics〔M〕. Cambridge： Cambridge University Press， 1997.

〔13〕 KHEEMENG K， ENGGUAN T. Counting〔M〕 . Singapore： World Scientific， 2013.

〔14〕 YOSEF R， MIZRACHI M， KADRAWI O. On Unimo-dality of Indenpen-dence Polynomials of Trees〔J〕. Discrete Mathematics， 2021， arXiv：2101.06744v4.

[1]	陈　丽, 朱兴文, 张朝元. 求解二维声波方程的高精度Runge-Kutta方法 [J]. 大理大学学报, 2023, 8(6): 20-23.
[2]	伍桂锋, 胡　伐, 曾　新, 杨邓奇, 李晓伟. MV-Raft：一种新的基于多维向量的联盟链共识算法 [J]. 大理大学学报, 2023, 8(6): 24-32.
[3]	唐　亮, 陆璟楠, 姜海锋, 薛九洋. 高管政治关联、环境监管模式变迁与企业环保投资 [J]. 大理大学学报, 2023, 8(6): 79-87.
[4]	熊　凯, 肖天保, 曾　炼, 罗字呈, 杨　桃, 杨胜邦. 苗药大乌泡对溃疡性结肠炎小鼠的治疗作用研究 [J]. 大理大学学报, 2023, 8(4): 1-6.
[5]	孟　东, 李　亚, 王重娟, 田　勇, 田云才, 吴明一. 蜗牛糖胺聚糖的含量测定及方法学验证 [J]. 大理大学学报, 2023, 8(4): 7-12.
[6]	王金玉, 周龙龙, 王学昌, 李晓东, 耿树琼, 夏从龙. 基于网络药理学和分子对接探讨乐脉颗粒治疗血管性痴呆的作用机制 [J]. 大理大学学报, 2023, 8(4): 13-21.
[7]	黄　山, 金礼权, 喻　宇, 黄　吉, 张峻华, 陈奕明. SOX9在小鼠肝卵圆细胞定向分化为胆管上皮细胞过程中的表达 [J]. 大理大学学报, 2023, 8(4): 22-27.
[8]	赵纯静, 陈卫国, 白　丽, 武有聪. 美洲大蠊提取物CⅡ-3对白假丝酵母菌生物膜形成的作用 [J]. 大理大学学报, 2023, 8(4): 28-33.
[9]	白宗凯, 吕　能, 刘润花, 罗元希, 吴秋玥, 徐　静, 武有聪. 健康大学生尿道外口酵母菌带菌率调查及药敏分析 [J]. 大理大学学报, 2023, 8(4): 34-38.
[10]	高文宇, 曾　蓉, 许梦娜, 张元元. EPAS1基因rs1868092位点多态性与中国藏族人群高原红细胞增多症的相关性研究 [J]. 大理大学学报, 2023, 8(4): 39-42.
[11]	刘如爱, 杨雪倩, 王播勇, 梅　雯, 周静华, 熊　伟. 人恶性胸膜间皮瘤组织中K-ras基因点突变的研究 [J]. 大理大学学报, 2023, 8(4): 43-49.
[12]	闫其星, 赵李妮, 唐文军, 陈进芳, 方　草. 卵巢癌患者MMP-9基因多态性与TP方案近期疗效的相关性研究 [J]. 大理大学学报, 2023, 8(4): 50-53.
[13]	张　茜, 常阿英, 杨正纯, 刘丽茹. 低钙与标准钙透析液分段枸橼酸抗凝血液透析的使用效果分析 [J]. 大理大学学报, 2023, 8(4): 54-59.
[14]	杨思丽, 罗万训, 王建萍. 双侧髂内动脉球囊临时阻断在完全性前置胎盘剖宫产中的应用 [J]. 大理大学学报, 2023, 8(4): 60-63.
[15]	高国玺, 胡建华, 杨　召, 张　俊, 张　超. 贝氏石膏制动治疗儿童股骨头骨骺骨软骨病的临床疗效分析 [J]. 大理大学学报, 2023, 8(4): 64-68.