Critical Groups for Complete Multipartite Graphs and Cartesian Products of Complete Graphs

Brian Jacobson, Andrew Niedermaier, Victor Reiner

Research output: Contribution to journalArticle

39 Scopus citations

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 Kn1,...,nk, we describe the critical group structure completely. For Cartesian products of complete graphs Kn1x⋯x Knk, 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 n1,..., n k.

Original languageEnglish (US)
Pages (from-to)231-250
Number of pages20
JournalJournal of Graph Theory
Volume44
Issue number3
DOIs
StatePublished - Nov 2003

Keywords

  • Abelian sandpile
  • Cartesian product graph
  • Chip-firing
  • Complete multipartite graph
  • Critical group
  • Graph Laplacian
  • Matrix-tree theorem
  • Smith normal form

Fingerprint Dive into the research topics of 'Critical Groups for Complete Multipartite Graphs and Cartesian Products of Complete Graphs'. Together they form a unique fingerprint.

  • Cite this