Independent Number and Independent Polynomial of Complete Product of Graph

Abstract

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

CLC Number:

Yang Limin.

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

References

〔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]	Zhou Bin. Research on the Solution of Pure Integer Programming Problem Based on Number Theory [J]. Journal of Dali University, 2023, 8(6): 14-19.
[2]	Chen Li, Zhu Xingwen, Zhang Chaoyuan. The High-Precision Runge-Kutta Method for Solving Two-Dimensional Acoustic Wave Equation [J]. Journal of Dali University, 2023, 8(6): 20-23.
[3]	Wu Guifeng, Hu Fa, Zeng Xin, Yang Dengqi, Li Xiaowei. MV-Raft： A New Consensus Algorithm forAllianceChain Based on Multidimensional Vectors [J]. Journal of Dali University, 2023, 8(6): 24-32.
[4]	Cui Maohuan, Rao Dingqi. Diversity and Faunal Characteristics of Amphibians and Reptiles in Lanping Yunling Provincial Nature Reserve [J]. Journal of Dali University, 2023, 8(6): 61-68.
[5]	Li Jia, Yang Yingfei. A Dynamic Study on Students' Physical Fitness inDaliUniversity [J]. Journal of Dali University, 2023, 8(6): 69-74.
[6]	Tang Liang, Lu Jingnan, Jiang Haifeng, Xue Jiuyang. Executive Political Connections， Changes in Environmental Regulatory Modes， and Corporate Environmental Investment [J]. Journal of Dali University, 2023, 8(6): 79-87.
[7]	Ma Chenyu, Liu Chaorui, Lü Jianguo, Zhou Dongyan, Ye Zhilan. Analysis of Yield and Agronomic Traits of Maize Hybrids Bred from Inbred Line 2408 [J]. Journal of Dali University, 2023, 8(6): 88-94.
[8]	Xiong Kai, Xiao Tianbao, Zeng Lian, Luo Zicheng, Yang Tao, Yang Shengbang. Therapeutic Effect of Miao Medicine Rubus pluribracteatus on Mice with Ulcerative Colitis [J]. Journal of Dali University, 2023, 8(4): 1-6.
[9]	Meng Dong, Li Ya, Wang Chongjuan, Tian Yong, Tian Yuncai, Wu Mingyi. Content Determination and Methodological Validation of Snail Glycosaminoglycan [J]. Journal of Dali University, 2023, 8(4): 7-12.
[10]	Wang Jinyu, Zhou Longlong, Wang Xuechang, Li Xiaodong, Geng Shuqiong, Xia Conglong. Investigation on the Mechanism of Lemai Granules in the Treatment of Vascular Dementia Based on Network Pharmacology and Molecular Docking [J]. Journal of Dali University, 2023, 8(4): 13-21.
[11]	Huang Shan, Jin Liquan, Yu Yu, Huang Ji, Zhang Junhua, Chen Yiming. Expression of SOX9 in the Directed Differentiation of Mouse Hepatic Oval Cell into Biliary Epithelial Cells [J]. Journal of Dali University, 2023, 8(4): 22-27.
[12]	Zhao Chunjing, Chen Weiguo, Bai li, Wu Youcong. Effects of Periplaneta americana Extract CⅡ-3 on the Biofilm Formation of Candida albicans [J]. Journal of Dali University, 2023, 8(4): 28-33.
[13]	Bai Zongkai, Lü Neng, Liu Runhua, Luo Yuanxi, Wu Qiuyue, Xu Jing, Wu Youcong. Investigation on the Carrier Rate and Antifungal Susceptibility of Yeast Species Isolated from External Urethral Meatus of Healthy College Students [J]. Journal of Dali University, 2023, 8(4): 34-38.
[14]	Gao Wenyu, Zeng Rong, Xu Mengna, Zhang Yuanyuan. Study on the Correlation between Polymorphism of EPAS1 Gene rs1868092 and High Altitude Polycythemia in Tibetan Population [J]. Journal of Dali University, 2023, 8(4): 39-42.
[15]	Liu Ruai, Yang Xueqian, Wang Boyong, Mei Wen, Zhou Jinghua, Xiong Wei. Research on the Point Mutation of K-ras Gene in Human Malignant Pleural Mesothelioma [J]. Journal of Dali University, 2023, 8(4): 43-49.