Generalized diameters and Rabin numbers of networks (Q1288475): Difference between revisions

In a graph the (unweighted) distance between two vertices \(x\) and \(y\) is defined to be the minimum number of edges of a path from \(x\) to \(y\). Concerning reliability and efficiency of a graph (seen as a network) simultaneously, it makes sense to look for disjoint paths between \(x\) and \(y\) which are all not too long. Parameters ``\(w\)-wide diameters \((G)\)'', ``\((w-1)\)-fault diameters \((G)\)'', ``\(w\)-Rabin numbers \((G)\)'', and ``strong \(w\)-Rabin numbers \((G)\)'' have been defined to measure such mixed properties of a network via worst case tuples of vertices in \(G\). In the paper the exact values for these parameters are proved for several classes of relevant graphs: circulant networks, \(d\)-ary cube networks, generalized hypercube networks, folded hypercube networks, and WK-recursive networks. It turns out that in almost all classes the parameters are almost independent of the value of \(w\). (The only exception is for WK-recursive networks and \(w=1\) versus \(w>1\).) Results for average case tuples of vertices are not proved. Probably they are much harder to achieve.