Asymptotic enumeration of vertex-transitive graphs of fixed valency

详细信息    查看全文

• 作者：Primož Potočnik^a ; ^b ; ^c ; ^{primoz.potocnik@fmf.uni-lj.si} ; Pablo Spiga^d ; ^{pablo.spiga@unimib.it} ; Gabriel Verret^e ; ^f ; ^{gabriel.verret@uwa.edu.au}
• 关键词：Cubic ; 3-Valent ; Vertex-transitive ; Cayley ; GRR ; Enumeration
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：221-240
• 全文大小：462 K
• 卷排序：122

文摘

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)Cay(G,S) has vertex-set G and two vertices u and v   are adjacent if and only if uv−1∈Suv−1∈S. Let CAYd(n)CAYd(n) be the number of isomorphism classes of d-valent Cayley graphs of order at most n  . We show that log⁡(CAYd(n))∈Θ(d(log⁡n)2)log⁡(CAYd(n))∈Θ(d(log⁡n)2), as n→∞n→∞. We also obtain some stronger results in the case d=3d=3.