On Critical Groups Of Graphs

The Laplacian matrix is a powerful tool in graph theory. Traditionally, the people use the eigenvalues of the Laplacian matrix to describe the properties of graphs and get a lot of very nice results. In the last twenty years, the Smith normal form of L(G) is found to be the fine invariant of isomorphism on graphs as well as the Laplacian eigenvalues, so it is meaningful to pay our attention to the Smith normal form of L(G). We know the critical group from GTM 207, while the famous mathematician N.Biggs stated that the critical group of a graph is depend on its Smith normal form in 1999. In this thesis we describe the Smith normal forms of two kinds of Cartesian product graphs:Km×Cn and C4×Cn. Then we get their critical groups and the spanning tree numbers. In the last chapter of this thesis we will show the sharp upper bounds of the first three invariant factors of the Smith normal form of graph G.The followings are the main results where the parameters will be explained in the corresponding part of the main text.If n= 2s+1, then the critical group of Km×Cn (m, n≥3) is If n= 2s, then the critical group of Km×Cn (m, n≥3) is where Then the number of spanning trees of Km×Cn is If n= 2s+1, then the critical group of C4×Cn(n≥3) is If n= 2s with s odd, then the critical group of C4×Cn(n≥3) is If n= 2s with s even, then the critical group of C4×Cn (n≥3) is Then the number of spanning trees of C4 x Cn is So, if n≥3, the following equation holds. Further more,for a simple connected graph G≠Kn with order n≥5,the third invariant factor s3 is described as follow:s3(G)≤n and s3(G)=n if and only if G=Kn-e,where e is an edge of Kn；s3(G)=n-1 if and only if G=v·Kn-1; s3(G)=n-2 if and only if n=5 and G=K5-2e or G=K5-C4;s3(G)=n-3 if and only if G is one of the following graphs:K2,3,K5-C3,K6-C3,K7-2C3, K3,3 and K7-K3,3.