The diameters of almost all Cayley digraphs
type: Item
instance of: scholarly article
title: The diameters of almost all Cayley digraphs
zbMATH Open document ID: 0889.05054
DOI: 10.1007/BF02009550
author: Xin Liu
author: Jixiang Meng
published in: Acta Mathematicae Applicatae Sinica. English Series
publication date: 1998-06-11T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 1104085
zbMATH Keywords: Cayley digraphs
zbMATH Keywords: probability
zbMATH Keywords: diameter
zbMATH Keywords: strongly connected
reviewed by: Ulrike Baumann
MaRDI profile type: Publication
cites work: On the connectivity of Cayley digraphs
cites work: A survey: Hamiltonian cycles in Cayley graphs
cites work: Q3669446
cites work: The minimum order of a cayley graph with given degree and diameter
cites work: A group-theoretic model for symmetric interconnection networks
cites work: Minimal diameter double-loop networks: Dense optimal families
cites work: A note on partial Cayley graphs
cites work: Q3950588
cites work: On the automorphism groups of almost all Cayley graphs
cites work: On the full automorphism group of a graph
cites work: Q3097395
cites work: Q4770409
cites work: Q4197800
cites work: Q4121925
cites work: Almost all steinhaus graphs have diameter 2
cites work: Probability of diameter two for Steinhaus graphs
full work available at URL: https://doi.org/10.1007/bf02009550
OpenAlex ID: W2034733662
description: scientific article; zbMATH DE number 1104085