Arithmetical Semirings
arXiv:1605.08640 · doi:10.1016/j.disc.2019.03.021
Abstract
We study the number of connected graphs with vertices that cannot be written as the cartesian product of two graphs with fewer vertices. We give an upper bound which implies that for large almost all graphs are both connected and cartesian prime. For graphs with an even number of vertices, a full asymptotic expansion is obtained. Our method, inspired by Knopfmacher's theory of arithmetical semigroups, is based on reduction to Wright's asymptotic expansion for the number of connected graphs with vertices.
18 pages, enhanced exposition, minor corrections