Gossiping and routing in second-kind Frobenius graphs

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⋊HG=K⋊H, where KK is a nilpotent normal subgroup of GG. A second-kind GG-Frobenius graph is a Cayley graph Γ=Cay(K,aH∪(a−1)H) for some a∈Ka∈K with order ≠2≠2 and 〈aH〉=K〈aH〉=K, where HH is of odd order and xHxH denotes the HH-orbit containing x∈Kx∈K. In the case when KK is abelian of odd order, we give the exact value of the minimum gossiping time of ΓΓ under the store-and-forward, all-port and full-duplex model and prove that ΓΓ 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 KK is abelian of even order, we give an upper bound on the minimum gossiping time of ΓΓ under the same model. When KK 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 ΓΓ, and prove that such routings are also optimal for arc-forwarding and minimal arc-forwarding indices if in addition KK 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≥4r≥4, there exist infinitely many second-kind Frobenius graphs with valency rr and order greater than any given integer such that the kernels of the underlying Frobenius groups are abelian of odd order.