The critical group of a threshold graph

Hans Christianson, Victor Reiner

Research output: Contribution to journalArticlepeer-review

29 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

Bibliographical note

Funding Information:
This paper arose from work supported by the Summer 2000 and 2001 University of Minnesota Research Experiences for Undergraduates (REU) program, and partly supported by NSF grant DMS-9877047. The authors thank Paul Bendich and Tristram Bogart for conjecturing Theorem 10 based on extensive computer explorations, and thank Hyung Kim for the crucial computer explorations which led to Conjecture 7. They also thank Dan Drake and David Treumann for helpful conversations.

Publisher Copyright:
© 2002 Elsevier Science Inc. All rights reserved.

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