The diameters of almost all Cayley digraphs (Q1375344): Difference between revisions

The authors consider Cayley digraphs of finite groups. Let \(G\) be a group and \(S\) a subset of \(G\) not containing the identity. The Cayley digraph \(X(G,S)\) of \(G\) with respect to \(S\) is a digraph whose vertex set is \(G\) and such that, for all \(x,y\in G\), there is an arc from \(x\) to \(y\) in \(X(G,S)\) iff \(x^{-1} y\in S\). A probability measure is assigned by requiring \(\text{P} (a \in S) =p\) for any \(a\in G\setminus \{1\}\). It is shown that the probability of the set of Cayley digraphs of \(G\) with diameter 2 approaches 1 as the order of \(G\) approaches infinity, i.e. almost all Cayley digraphs have diameter 2. Moreover it is shown that (i) almost all Cayley digraphs are strongly connected; (ii) almost all subsets of \(G\) are generating subsets of \(G\); and (iii) the arc-connectivities of almost all Cayley digraphs are their regular degrees.