Asymptotic enumeration of vertex-transitive graphs of fixed valency

DOI10.1016/J.JCTB.2016.06.002zbMATH Open1350.05064arXiv1210.5736OpenAlexW1514154349MaRDI QIDQ345083FDOQ345083

Pablo Spiga, Primož Potočnik, Gabriel Verret

Publication date: 25 November 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: Let $G$ be a group and let $S$ be an inverse-closed and identity-free generating set of $G$. The emph{Cayley graph} $Cay(G,S)$ has vertex-set $G$ and two vertices $u$ and $v$ are adjacent if and only if $u{v}^{-1}inS$. Let $CA{Y}_d(n)$ be the number of isomorphism classes of $d$-valent Cayley graphs of order at most $n$. We show that $log(CA{Y}_d(n))inTheta(d(logn{)}^2)$, as $noinfty$. We also obtain some stronger results in the case $d=3$.

Full work available at URL: https://arxiv.org/abs/1210.5736

Recommendations

• Enumeration of isomorhism types of Cayley graphs of small valencies on dihedral groups
• On the asymptotic enumeration of Cayley graphs
• Some properties of Cayley graphs on symmetric groups \(S_n\)
• Asymptotic enumeration of Cayley digraphs
• The structure of Cayley graphs of dihedral groups of valencies 1, 2 and 3

zbMATH Keywords

enumerationCayley graphcubic graphvertex-transitive graph3-valent graphgraphical regular representation (GRR)

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Enumeration in graph theory (05C30)

Cites Work

• Lie Representations and Groups of Prime Power Order
• Sur les groupes nilpotents et les anneaux de Lie
• ENUMERATING FINITE GROUPS
• Title not available (Why is that?)
• The automorphism groups of some cubic Cayley graphs
• On the Symmetry of Cubic Graphs
• Über die Faktorgruppen einer absteigenden Zentralreihe
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the full automorphism group of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the automorphism groups of almost all Cayley graphs
• Cayley graphs on abelian groups
• Normal growth of large groups. II.
• Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs
• Enumerating Groups Acting Regularly on a d-Dimensional Cube
• Bounding the size of a vertex-stabiliser in a finite vertex-transitive graph
• Title not available (Why is that?)
• Automorphisms of Cayley graphs on generalised dicyclic groups
• Title not available (Why is that?)
• Finite primitive permutation groups and regular cycles of their elements.
• AN ENUMERATION THEOREM FOR FINITE GROUPS
• Enumerating boundedly generated finite groups.
• On the order of vertex-stabilisers in vertex-transitive graphs with local group \(\mathrm{C}_p \times \mathrm{C}_p\) or \(\mathrm{C}_p\, \mathrm{wr}\, \mathrm{C}_2\)

Cited In (8)

• Vertex transitive graphs G with χ_D(G) > χ(G) and small automorphism group
• Three local actions in 6‐valent arc‐transitive graphs
• Enumerating graphs via even/odd dichotomy
• Random Schreier graphs and expanders
• Asymptotic enumeration of Cayley digraphs
• Lifting a prescribed group of automorphisms of graphs
• On the existence and the enumeration of bipartite regular representations of Cayley graphs over abelian groups
• Cayley graphs on abelian groups

This page was built for publication: Asymptotic enumeration of vertex-transitive graphs of fixed valency

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q345083)