The critical group of a threshold graph

Hans Christianson, Victor Reiner

Research output: Contribution to journalArticle

28 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. The structure of this group is a subtle isomorphism invariant that has received much attention recently, partly due to its relation to the graph Laplacian and chip-firing games. However, the group structure has been determined for relatively few classes of graphs. Based on computer evidence, we conjecture the exact group structure for a well-studied class of graphs having integer spectra, the threshold graphs, and prove this conjecture for the subclass which we call generic threshold graphs.

Original languageEnglish (US)
Pages (from-to)233-244
Number of pages12
JournalLinear Algebra and Its Applications
Volume349
Issue number1-3
DOIs
StatePublished - Jul 21 2002

Keywords

  • Abelian sandpile
  • Chip-firing
  • Critical group
  • Graph Laplacian
  • Matrix-tree theorem
  • Picard group
  • Smith normal form
  • Threshold graph

Fingerprint Dive into the research topics of 'The critical group of a threshold graph'. Together they form a unique fingerprint.

  • Cite this