Back to Search
Start Over
Counting arithmetical structures on paths and cycles
- Source :
- Discrete Mathematics. 341:2949-2963
- Publication Year :
- 2018
- Publisher :
- Elsevier BV, 2018.
-
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 2 n − 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.
- Subjects :
- Discrete mathematics
Mathematics::Combinatorics
Mathematics - Number Theory
010102 general mathematics
0102 computer and information sciences
01 natural sciences
Theoretical Computer Science
Combinatorics
Catalan number
010201 computation theory & mathematics
FOS: Mathematics
Torsion (algebra)
Enumeration
Mathematics - Combinatorics
Discrete Mathematics and Combinatorics
Arithmetic function
Combinatorics (math.CO)
Number Theory (math.NT)
Adjacency matrix
0101 mathematics
Laplace operator
Connectivity
Binomial coefficient
Mathematics
Subjects
Details
- ISSN :
- 0012365X
- Volume :
- 341
- Database :
- OpenAIRE
- Journal :
- Discrete Mathematics
- Accession number :
- edsair.doi.dedup.....2179d935d09236897bd4c48ab301eef3