节点文献
单层圆柱形网格图的独立多项式和Merrifeld-Simmons指数（英文）
Independence Polynomials and the Merrifield-Simmons Index of Mono-Layer Cylindrical Grid Graphs
【摘要】 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■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.
【Abstract】 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■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.
【Key words】 Independence polynomial； Cylindrical grid graphs； Transfer matrix； Merrifield-Simmons index；
- 【文献出处】 Chinese Quarterly Journal of Mathematics ,数学季刊(英文版) , 编辑部邮箱 ,2024年04期
- 【分类号】O157.5
- 【下载频次】10