The Critical Group Of Several Classes Of Graphs

The critical group of a connected graph,also known as the sandpile group or Jacobian group,is a finite abelian group,whose order is the number of spanning trees in the graph.It is closely connected with the Laplacian matrix of the graph,as well as with the cycle space and the bond space.In this paper,we have completely determined the structure of the critical group of the nearly complete graph K_n-C_kand the almost complete bipartite graph K_m,n-p K₂by calculating the Smith normal form of the reduced Laplacian matrix of the corresponding graph,where K_n-C_kdenotes the graph obtained from the complete graph K_nby removing the k edges of a cycle C_kand K_m,n-p K₂denotes the graph obtained from the complete bipartite graph K_m,nby deleting a matching of size p.Our results show that the critical group of these two kinds of graphs are not cyclic except for a few small graphs.Thus,we prove Lorenzini’s conjecture that the critical group of K_n-C_nis not cyclic for the first time.And we also give another proof of the conjecture that the critical group of K_n-C_n-1is not cyclic.Meanwhile,the number of spanning trees of the two kinds of graphs can be obtained directly as corollaries of our results.