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.

DOI

10.1016/j.disc.2018.07.002

Version

Pre-print

Required Publisher's Statement

The original article can be found on the publisher's website: https://www.sciencedirect.com/science/article/pii/S0012365X18302188

Included in

Mathematics Commons

Share

COinS