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...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.展开更多
基金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.
