有限群具有测地Cayley图

Finite groups with geodetic Cayley graphs

摘要 Abstract

若连通无向图中每对顶点之间存在唯一最短路径,则称该图为“测地”的。有人猜测对于有限群,仅奇数阶循环图和完全图是测地Cayley图。本文提出了一系列理论结果,为计算机搜索验证这一猜想适用于所有不超过1024阶的群提供了支持。该猜想还被验证适用于若干无限族的群,包括二面体群以及某些幂零群的族。使计算机搜索能够达到如此规模的两个关键结果是:若群的中心具有偶数阶,则该猜想成立(这排除了我们的计算机搜索中的所有2-群);若Cayley图是测地的,则群的大小、生成集及中心之间存在一些限制关系(显著减少了必须搜索的生成集数量)。

A connected undirected graph is called \emph{geodetic} if for every pair of vertices there is a unique shortest path connecting them. It has been conjectured that for finite groups, the only geodetic Cayley graphs are odd cycles and complete graphs. In this article we present a series of theoretical results which contribute to a computer search verifying this conjecture for all groups of size up to 1024. The conjecture is also verified for several infinite families of groups including dihedral and some families of nilpotent groups. Two key results which enable the computer search to reach as far as it does are: if the center of a group has even order, then the conjecture holds (this eliminates all $2$-groups from our computer search); if a Cayley graph is geodetic then there are bounds relating the size of the group, generating set and center (which significantly cuts down the number of generating sets which must be searched).