Laplacian Matrix And Critical Group Of A Graph

Enormous progress has been achieved in development of the theory concerned to Laplacian matrix and Tutte polynomial since both of these two concepts are considered as the most powerful tools in studying the properties of graph.The Chip-firing games, which has been founded on the connected graph,may quite relate to the Laplacian matrix and Tutte polynomial.Therefore in this dissertation,we will apply these tools to investigate several propositions corresponding to the game model.The paper is organized as follows:In the first Chapter,we will introduce the basic concepts in graph theory and other associated definition of production of graphs.In addition,a brief review on Laplace matrix and Tutte polynomial would be presented in this chapter.Starting from the preliminaries in Chapter 1,unimodular equivalence and congruence of Laplacian matrix and its edge version of a graph will be deeply discussed. Specifically,we give the graph whose Laplacian matrix can unimodularly congruent to its Smith normal form.In Chapter 3,we investigate the Chip-firing game and its extension(the dollar game).The research in this chapter will mainly focus on the properties of the game and the critical group of the graph.Then,we give a bijection between critical configuration and spanning tree,and the relationship between critical configuration and Tutte polynomial is further discussed.The detailed calculation of critical group of graph will be given in Chapter 4.we introduce the generator method in calculation the critical group.Based on the results derived in previous research,we give the critical group of some kinds of cartesian product graph.We prove that the critical group of the cartesian product graph K_m×P_n is always the direct sum of m-1 cyclic groups.And we also give the result of the critical groups of K_m×C_n and C₅×C_n.At last,we obtained some result about the the critical group of totally connected graphs.