Wide Diameter and Diameter of Networks

Abstract

A container \(C(x,y)\) is a set of vertex-disjoint paths between vertices \(z\) and \(y\) in a graph \(G\). The width \(w(C(x,y))\) and length \(L(C(x,y))\) are defined to be \(|C(x,y)|\) and the length of the longest path in \(C(x,y)\) respectively. The \(w\)-wide distance \(d_w(x,y)\) between \(x\) and \(y\) is the minimum of \(L(C(x,y))\) for all containers \(C(x,y)\) with width \(w\). The \(w\)-wide diameter \(d_w(G)\) of \(G\) is the maximum of \(d_w(x,y)\) among all pairs of vertices \(x,y\) in \(G\), \(x \neq y\). In this paper, we investigate some problems on the relations between \(d_w(G)\) and diameter \(d(G)\) which were raised by D.F. Hsu \([1]\). Some results about graph equation of \(d_w(G)\) are proved.