TY - JOUR

T1 - Counting arithmetical structures on paths and cycles

AU - Braun, Benjamin

AU - Corrales, Hugo

AU - Corry, Scott

AU - Puente, Luis David García

AU - Glass, Darren

AU - Kaplan, Nathan

AU - L. Martin, Jeremy

AU - Musiker, Gregg

AU - Valencia, Carlos E.

PY - 2018/10/1

Y1 - 2018/10/1

N2 - © 2018 Elsevier B.V. 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.

AB - © 2018 Elsevier B.V. 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.

UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85050548675&origin=inward

UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=85050548675&origin=inward

U2 - 10.1016/j.disc.2018.07.002

DO - 10.1016/j.disc.2018.07.002

M3 - Article

SP - 2949

EP - 2963

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

ER -