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\ne 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.