Manuel E. Lladser ; Primož Potočnik ; Jozef Širáň ; Mark C. Wilson - Random Cayley digraphs of diameter 2 and given degree

dmtcs:588 - Discrete Mathematics & Theoretical Computer Science, September 10, 2012, Vol. 14 no. 2 -
Random Cayley digraphs of diameter 2 and given degreeArticle

Authors: Manuel E. Lladser 1; Primož Potočnik 2; Jozef Širáň 3,4; Mark C. Wilson 5

  • 1 Department of Applied Mathematics [Boulder]
  • 2 Faculty of Mathematics and Physics [Ljubljana]
  • 3 School of Mathematics and Statistics [Milton Keynes]
  • 4 Department of Mathematics and Descriptive Geometry [Bratislava]
  • 5 Department of Computer Science [Auckland]

We consider random Cayley digraphs of order n with uniformly distributed generating sets of size k. Specifically, we are interested in the asymptotics of the probability that such a Cayley digraph has diameter two as n -> infinity and k = f(n), focusing on the functions f(n) = left perpendicularn(delta)right perpendicular and f(n) = left perpendicularcnright perpendicular. In both instances we show that this probability converges to 1 as n -> infinity for arbitrary fixed delta is an element of (1/2, 1) and c is an element of (0, 1/2), respectively, with a much larger convergence rate in the second case and with sharper results for Abelian groups.

Volume: Vol. 14 no. 2
Section: Graph Theory
Published on: September 10, 2012
Accepted on: June 9, 2015
Submitted on: August 25, 2011
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 395 times.
This article's PDF has been downloaded 314 times.