Counting arithmetical structures on paths and cycles

Benjamin Braun, Hugo Corrales, Scott Corry, Luis David García Puente, Darren Glass, Nathan Kaplan, Jeremy L. Martin, Gregg Musiker, Carlos E. Valencia

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

Let G be a finite, connected graph. An arithmetical structure on G is a pair of positive integer vectors d,r such that (diag(d)−A)r=0, where A is the adjacency matrix of G. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the torsion part of the cokernels of the matrices (diag(d)−A)). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients [Formula presented], and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.

Original languageEnglish (US)
Pages (from-to)2949-2963
Number of pages15
JournalDiscrete Mathematics
Volume341
Issue number10
DOIs
StatePublished - Oct 2018

Bibliographical note

Publisher Copyright:
© 2018 Elsevier B.V.

Keywords

  • Arithmetical graph
  • Ballot number
  • Catalan number
  • Critical group
  • Laplacian
  • Sandpile group

Fingerprint

Dive into the research topics of 'Counting arithmetical structures on paths and cycles'. Together they form a unique fingerprint.

Cite this