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 language | English (US) |
|---|---|
| Pages (from-to) | 233-244 |
| Number of pages | 12 |
| Journal | Linear Algebra and Its Applications |
| Volume | 349 |
| Issue number | 1-3 |
| DOIs | |
| State | Published - 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