DIMACS TR: 2002-30

On the Edge-Forwarding Indices of Frobenius Graphs

Authors: Yan Wang, Xin Gui Fang, and D. Frank Hsu


A $G$-Frobenius graph, as defined recently by Fang, Li, and Praeger, is a connected orbital graph of a Frobenius group $G=K{:}H$ with Frobenius kernel $K$ and Frobenius complement $H$. $\Gamma$ is also shown to be a Cayley graph, $\Gamma=Cay(K,S)$ for $K$ and some subset $S$ of the group $G$. On the other hand, a network $N$ with a routing function $R$, written as $(N,R)$, is an undirected graph $N$ together with a routing $R$ which consists of a collection of simple paths connecting every pair of vertices in the graph. The edge-forwarding index $\pi(\Gamma)$ of a network $(N,R)$, defined by Heydemann, Meyer, and Sotteau, is a parameter to describe the maximum load of edges of $N$. In this paper, we study the edge-forwarding index of Frobenius graphs. In particular, we obtain edge-forwarding index of a $G$-Frobenius graph $\Gamma$ with rank$(G)\leq 50$ and those of $\Gamma$ which has $type-(n_1,n_2,...,n_d)$ where $d=n,(1,2,3,...,n); d=2n-1,(1,2,...,n-1,n,n-1,...,2,1); d=2n,(1,2,...,n-1,n,n,n-1,...2,1)$, respectively.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-30.ps.gz
DIMACS Home Page