Counting Arithmetical Structures on Paths and Cycles

Abstract

Let $G$ be a finite, simple, connected graph. An arithmetical structure on $G$ is a pair of positive integer vectors $\mathbf{d},\mathbf{r}$ such that $(\mathrm{diag}(\mathbf{d})-A)\mathbf{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 cokernels of the matrices $(\mathrm{diag}(\mathbf{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 $\left(\genfrac{}{}{0ex}{}{2n-1}{n-1}\right)$, and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.

Jesse Geneson discovered an error in the final sentence of Proposition 33. The sentence should read, "In particular, the number of arithmetical $r$-structures on $C_n$ with $r_i=1$ is the Catalan number $C_{n-1}$." The published version mistakenly refers to $d$-structures instead of $r$-structures

References in corpus (1)

• Arithmetic infinite friezes from punctured discs

Cited by in corpus (10)

• Arithmetical structures on bidents
• Bounding the number of arithmetical structures on graphs
• Chip-Firing Games and Critical Groups
• Counting Finite Index Subrings of ${\mathbb{Z}}^n$
• Frieze Vectors and Unitary Friezes
• Abelian networks IV. Dynamics of nonhalting networks
• On Arithmetical Structures on Complete Graphs
• Critical groups of arithmetical structures under a generalized star-clique operation
• Algorithmic aspects of arithmetical structures
• Critical groups of arithmetical structures on star graphs and complete graphs