Critical groups for complete multipartite graphs and Cartesian products of complete graphs
- 1 October 2003
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 44 (3) , 231-250
Abstract
The critical group of a connected graph is a finite abelian group, whose order is the number of spanning trees in the graph, and which is closely related to the graph Laplacian. Its group structure has been determined for relatively few classes of graphs, e.g., complete graphs and complete bipartite graphs. For complete multipartite graphs $K_{n_{1},\ldots, {n_k}}$ , we describe the critical group structure completely. For Cartesian products of complete graphs $K_{n_{1}} \times \cdots \times K_{n_{k}}$ , we generalize results of H. Bai on the k‐dimensional cube, by bounding the number of invariant factors in the critical group, and describing completely its p‐primary structure for all primes p that divide none of $n_1, \ldots, n_k$ . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 231–250, 2003
Keywords
This publication has 10 references indexed in Scilit:
- On the critical group of the n-cubeLinear Algebra and its Applications, 2003
- Algebraic Graph Theory2001
- On the Sandpile Group of Dual GraphsEuropean Journal of Combinatorics, 2000
- The number of spanning trees of a complete multipartite graphDiscrete Mathematics, 1999
- The number of spanning trees of a complete multipartite graphDiscrete Mathematics, 1999
- Chip-Firing and the Critical Group of a GraphJournal of Algebraic Combinatorics, 1999
- Algebraic Potential Theory on GraphsBulletin of the London Mathematical Society, 1997
- Algebraic aspects of Abelian sandpile modelsJournal of Physics A: General Physics, 1995
- A finite group attached to the laplacian of a graphDiscrete Mathematics, 1991
- Self-organized critical state of sandpile automaton modelsPhysical Review Letters, 1990