Document Type
Article
Publication Date
7-27-2018
Department 1
Mathematics
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 ((2n-1)/(n-1)) , and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.
Copyright Note
This is the author's version of the work. This publication appears in Gettysburg College's institutional repository by permission of the copyright owner for personal use, not for redistribution.
DOI
10.1016/j.disc.2018.07.002
Version
Pre-print
Recommended Citation
Braun, Benjamin, Hugo Corrales, Scott Corry, Luis David García Puente, Darren Glass, Nathan Kaplan, Jeremy L. Martin, Gregg Musiker, and Carlos E.Valencia. "Counting Arithmetical Structures on Paths and Cycles." Discrete Mathematics, 341, no. 10 (2018): 2949–2963.
Required Publisher's Statement
The original article can be found on the publisher's website: https://www.sciencedirect.com/science/article/pii/S0012365X18302188