Summary: A Frobenius group is a permutation group which is transitive but not regular such that only the identity element can fix two points. It is well known that such a group is a semidirect product \(G = K \rtimes H\), where \(K\) is a nilpotent normal subgroup of \(G\). A second-kind \(G\)-Frobenius graph is a Cayley graph \(\Gamma=\)Cay\((K,a^{H} \cup (a^{-1})^{H})\) for some \(a\in K\) with order \(\neq 2\) and \(\langle a^{H}\rangle =K\), where \(H\) is of odd order and \(x^{H}\) denotes the \(H\)-orbit containing \(x\in K\).
In the case when \(K\) is abelian of odd order, we give the exact value of the minimum gossiping time of \(\Gamma \) under the store-and-forward, all-port and full-duplex model and prove that \(\Gamma \) admits optimal gossiping schemes with the following properties: messages are always transmitted along shortest paths; each arc is used exactly once at each time step; at each step after the initial one the arcs carrying the message originated from a given vertex form a perfect matching.
In the case when \(K\) is abelian of even order, we give an upper bound on the minimum gossiping time of \(\Gamma \) under the same model. When \(K\) is abelian, we give an algorithm for producing all-to-all routings which are optimal for both edge-forwarding and minimal edge-forwarding indices of \(\Gamma \), and prove that such routings are also optimal for arc-forwarding and minimal arc-forwarding indices if in addition \(K\) is of odd order.
We give a family of second-kind Frobenius graphs which contains all Paley graphs and connected generalized Paley graphs of odd order as a proper subfamily. Based on this and Dirichlet’s prime number theorem we show that, for any even integer \(r\geq 4\), there exist infinitely many second-kind Frobenius graphs with valency \(r\) and order greater than any given integer such that the kernels of the underlying Frobenius groups are abelian of odd order.