The edge-forwarding index or orbital regular graphs (Q1331968): Difference between revisions

Let \(\Gamma\) denote a finite simple undirected graph on \(n\) vertices. A routing \(R\) is a set of \(n(n-1)\) paths in \(\Gamma\) such that each of the ordered pairs of distinct vertices is joined by one of them. The edge- forwarding index \(\Pi(\Gamma)\) is the minimum over all routings \(R\) of the maximum over all edges \(e\) of the number of paths in \(R\) that traverse \(e\). The so-called merit factor is defined to be \[ f(\Gamma)= {\Pi(\Gamma) \Delta\ln(\Delta-1)\over n\ln n}, \] where \(\Delta\) denotes the maximum valence of \(\Gamma\). The graph \(\Gamma\) is said to be orbital regular if some subgroup of its automorphism group acts reguarly on each of the orbits of unordered pairs of distinct vertices of \(\Gamma\), the edge-set \(E\) of \(\Gamma\) being one of these orbits. For such graphs it is shown that \(\Pi(\Gamma)= (1/| E|)\sum d(u,v)\), where the summation is over all \((u,v)\in V\times V\) and \(d\) is the usual distance function. Consider in particular the Cayley graph \(\Gamma_{t,q}\) of the addition group of the field on \(q\) elements with respect to the generating set of (nonzero) \(t\)-adic residues. When \(t= 2\), the Paley graph \(P_ q\) is obtained and \(\Pi(P_ q)= 6\). More generally, \(f(\Gamma_{t,q})\leq 9/2+ o(1)\).