The Independence Polynomials And Minimum Fundamental Cycle Bases Of Graphs

Firstly,we studied the independence polynomial.The independence polynomial?;?of a graphis?;?=??₆=0)^??6)⁶),where6)is the number of independent sets of size6)inand??is the size of a maximum independent set.Vadim E.Levit and Eugen Mandrescu proved that the independence polynomial ofsatisfies|?;-1?|?2^??for any graph,where??is cyclomatic number of.In this paper,we will prove the bounds of the independence polynomial at=-1.?1?The independence polynomial of a grid at=-1 is bounded.?2?By considering the structure of graph,we obtained the following results:?i?If the cycles ofare not all??3cycles,then|?;-1?|?2^??-??;?ii?Ifis connected and has no pendant vertex,then|?;-1?|?2^??-1;?iii?If the cycles ofare not all??3 cycles andhas no pendant vertex,then|?;-1?|?2^??-1.Secondly,we studied the matching polynomial.The matching polynomial?;?of a graphis?;?=??₆=0)(6₆)⁶),where(6₆)is the number of matchings of size6)inandis the size of a maximum matching of.We determined the value?;-1?for paths,cycles,complete graphs and complete bipartite graphs.We proved that|?;-1?|?6 if??=2 andhas no pendant vertex andis connected.Finally,we determined the minimum fundamental cycle basis of an?9?-3)-regular bipartite graph with order 29).We constructed a fundamental cycle basis ofand proved this basis is a minimum fundamental cycle basis,we also determined the spanning tree corresponding to it.