Independence Polynomials and the Merrifield-Simmons Index of Mono-Layer Cylindrical Grid Graphs  

单层圆柱形网格图的独立多项式和Merrifield-Simmons指数

作　　者：JI Lin-xing ZHANG Ke HU Wen-jun 季琳星;张科;胡文军

机构地区：[1]School of Information Engineering,Huzhou University,Huzhou 313000,China

出　　处：《Chinese Quarterly Journal of Mathematics》2024年第4期379-387,共9页数学季刊（英文版）

基　　金：Supported by National Natural Science Foundation of China(Grant No.U20A20228);Huzhou Science and Technology Plan Project(Grant No.2022YZ53).

摘　　要：Research on the independence polynomial of graphs has been very active.However,the computational complexity of determining independence polynomials for general graphs remains NP-hard.Letα(G)be the independence number of G and i(G;k)be the number of independent sets of order k in G,then the independence polynomial is defined as I(G;x)=∑_(k=0)^(α(G))i(G;k)x^(k),i(G;0)=1.In this paper,by utilizing the transfer matrix,we obtain an analytical expression for I(CGn;x)of mono-cylindrical grid graphs CGn and present a crucial proof of it.Moreover,we also explore the Merrifield-Simmons index and other properties of CGn.

关 键 词：Independence polynomial Cylindrical grid graphs Transfer matrix Merrifield-Simmons index 

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