Affordable Access

Publisher Website

The critical group of a threshold graph

Authors
Journal
Linear Algebra and its Applications
0024-3795
Publisher
Elsevier
Publication Date
Volume
349
Identifiers
DOI: 10.1016/s0024-3795(02)00252-5
Keywords
  • Graph Laplacian
  • Critical Group
  • Picard Group
  • Abelian Sandpile
  • Chip-Firing
  • Smith Normal Form
  • Matrix-Tree Theorem
  • Threshold Graph

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.