The diameter of random Cayley digraphs of given degree

arXiv0706.3539MaRDI QIDQ6206003FDOQ6206003

Mark C. Wilson, Jana Šiagiová, Manuel E. Lladser, Primož Potočnik, Jozef Širáň

Publication date: 24 June 2007

Abstract: We consider random Cayley digraphs of order $n$ with uniformly distributed generating set of size $k$. Specifically, we are interested in the asymptotics of the probability such a Cayley digraph has diameter two as $noinfty$ and $k=f(n)$. We find a sharp phase transition from 0 to 1 at around $k=sqrtnlogn$. In particular, if $f(n)$ is asymptotically linear in $n$, the probability converges exponentially fast to 1.

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80)

This page was built for publication: The diameter of random Cayley digraphs of given degree

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