Asymptotic enumeration of vertex-transitive graphs of fixed valency

作者：Potocnik, Primoz^*; Spiga, Pablo; Verret, Gabriel

来源：Journal of Combinatorial Theory - Series B, 2017, 122: 221-240.

DOI：10.1016/j.jctb.2016.06.002

• Cubic
• 3-Valent
• Vertex-transitive
• Cayley
• GRR
• Enumeration

Let G be a group and let S be an inverse-closed and identity free generating set of G. The Cayley graph Cay(G, S) has vertex-set G and two vertices u and v are adjacent if and only if uv(-1) is an element of S. Let CAY(d)(n) be the number of isomorphism classes of d-valent Cayley graphs of order at most n. We show that log(CAY(d)(n)) is an element of circle minus(d(log n)(2)), as n -> infinity. We also obtain some stronger results in the case d = 3.

• 出版日期2017-1