Gossiping and routing in second-kind Frobenius graphs

Abstract

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⋊H, where K is a nilpotent normal subgroup of G. A second-kind G-Frobenius graph is a Cayley graph Γ=Cay(K,aH∪(a-1)H) for some a∈K with order ≠2 and 〈a H〉=K, where H is of odd order and x H denotes the H-orbit containing x∈K. In the case when K 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 alo..