Cayley-graph diameter and minimal-generator conjecture

Counterexample: every nonabelian dihedral group violates the conjecture

Let $g_{\min}(G)$ denote the minimum cardinality of a generating set of a finite group $G$. Barket, Grimaldi, Hendi, Hirst, Onus, and Singh, arXiv:2607.12026v1, Conjecture 4.2, conjecture that

$$\operatorname{diam}\!\left(\operatorname{Cay}(G,S)\right) \geq \frac{|G|}{g_{\min}(G)} \quad\Longrightarrow\quad G\cong (\mathbb Z/2\mathbb Z)^k \quad\text{for some }k\in\{2,3,4\}. \tag{1}$$

The source defines the diameter using the underlying undirected Cayley graph and allows an arbitrary, not necessarily minimal, generating set $S$. In fact, (1) fails even when $S$ is inverse-closed and has the smallest possible cardinality.

The smallest counterexample

Take

$$G=S_3, \qquad s=(12), \qquad t=(23), \qquad S=\{s,t\}. \tag{2}$$

Both generators are involutions, so $S=S^{-1}$ and there is no distinction between directed and undirected distances. Since $st$ is a $3$-cycle, $s$ and $t$ generate $S_3$. Moreover, $S_3$ is noncyclic, and consequently

$$|G|=6, \qquad |S|=g_{\min}(G)=2. \tag{3}$$

Every vertex of the Cayley graph has exactly two distinct neighbors. The graph is connected and has six vertices, so it is the cycle $C_6$. More explicitly, the distances from the identity are

$$\begin{array}{c|cccccc} x&1&s&t&st&ts&sts\\ \hline d(1,x)&0&1&1&2&2&3. \end{array} \tag{4}$$

By vertex-transitivity, these distances determine the diameter. Therefore

$$\operatorname{diam}\!\left(\operatorname{Cay}(S_3,\{(12),(23)\})\right) =3 =\frac{6}{2} =\frac{|S_3|}{g_{\min}(S_3)}. \tag{5}$$

Thus the hypothesis of (1) holds with equality, whereas $S_3$ is nonabelian and hence cannot be isomorphic to any elementary abelian $2$-group.

An infinite family of counterexamples

For every integer $r\geq 3$, let

$$D_{2r} =\left\langle s,t\;\middle|\; s^2=t^2=1,\ (st)^r=1 \right\rangle, \qquad S_r=\{s,t\}. \tag{6}$$

This is the dihedral group of order $2r$. It is nonabelian for $r\geq3$, so it is not cyclic. Since $S_r$ generates it, we obtain

$$|D_{2r}|=2r, \qquad |S_r|=g_{\min}(D_{2r})=2. \tag{7}$$

The two generators are distinct involutions. Hence the underlying Cayley graph is a connected, simple, $2$-regular graph on $2r$ vertices, necessarily

$$\operatorname{Cay}(D_{2r},S_r)\cong C_{2r}. \tag{8}$$

Its diameter is therefore

$$\operatorname{diam}\!\left(\operatorname{Cay}(D_{2r},S_r)\right) =r =\frac{|D_{2r}|}{g_{\min}(D_{2r})} \qquad (r\geq3). \tag{9}$$

None of these groups is elementary abelian. Consequently, the asserted structural implication fails for infinitely many nonabelian groups, already at order $6$.

The source's dataset selected only one particular generating set for each group. Its displayed $S_3$ example uses generators of orders $2$ and $3$, whose underlying Cayley graph has diameter $2$. Replacing them with the equally minimal generating set consisting of the two involutions in (2) changes the diameter to $3$. This dependence on the generating set explains why the counterexample need not appear in a one-generating-set-per-group census. The additional, unspecified suggestion about some further group property is not addressed here.