Asymptotic enumeration of vertex-transitive graphs of fixed valency

DOI10.1016/J.JCTB.2016.06.002MaRDI QIDQ345083zbMATH OpenOpenAlexFDO

Authors Primož Potočnik, Pablo Spiga, Gabriel Verret

Publication date 25 November 2016

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

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

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)

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$.

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

Cites work

• scientific article; zbMATH DE number 41228 (Why is no real title available?)
• scientific article; zbMATH DE number 558656 (Why is no real title available?)
• scientific article; zbMATH DE number 1750091 (Why is no real title available?)
• scientific article; zbMATH DE number 2151354 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• scientific article; zbMATH DE number 5272192 (Why is no real title available?)
• scientific article; zbMATH DE number 3046496 (Why is no real title available?)
• AN ENUMERATION THEOREM FOR FINITE GROUPS
• Automorphisms of Cayley graphs on generalised dicyclic groups
• Bounding the order of the vertex-stabiliser in 3-valent vertex-transitive and 4-valent arc-transitive graphs
• Bounding the size of a vertex-stabiliser in a finite vertex-transitive graph
• Cayley graphs on abelian groups
• ENUMERATING FINITE GROUPS
• Enumerating Groups Acting Regularly on a d-Dimensional Cube
• Enumerating boundedly generated finite groups.
• Finite primitive permutation groups and regular cycles of their elements.
• Lie Representations and Groups of Prime Power Order
• Normal growth of large groups. II.
• On the Symmetry of Cubic Graphs
• On the automorphism groups of almost all Cayley graphs
• On the full automorphism group of a graph
• 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\)
• Sur les groupes nilpotents et les anneaux de Lie
• The automorphism groups of some cubic Cayley graphs
• Über die Faktorgruppen einer absteigenden Zentralreihe

Cited in

(8)

• Three local actions in 6‐valent arc‐transitive graphs
• Enumerating graphs via even/odd dichotomy
• Random Schreier graphs and expanders
• Vertex transitive graphs \(G\) with \(\chi_D (G)>\chi(G)\) and small automorphism group
• 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)