Arithmetical Semirings
Copyright policy )Arithmetical Semirings
We study the number of connected graphs with $n$ 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 $n$ 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 $n$ vertices.
18 pages, enhanced exposition, minor corrections
Connectivity, product graphs, Graph operations (line graphs, products, etc.), Enumeration in graph theory, abstract analytic number theory, asymptotic enumeration, FOS: Mathematics, arithmetical semigroups, Mathematics - Combinatorics, Combinatorics (math.CO), graph enumeration
Connectivity, product graphs, Graph operations (line graphs, products, etc.), Enumeration in graph theory, abstract analytic number theory, asymptotic enumeration, FOS: Mathematics, arithmetical semigroups, Mathematics - Combinatorics, Combinatorics (math.CO), graph enumeration
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!