K-Diameter

[math]\displaystyle{ k }[/math]-Diameter --- [math]\displaystyle{ k }[/math]-диаметр.

Let [math]\displaystyle{ {\mathcal P}_{k}(u,v) = \{P_{1}, P_{2}, \cdots, P_{k}\} }[/math] be a family of [math]\displaystyle{ k }[/math] vertex disjoint paths between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] with lengths [math]\displaystyle{ |P_{1}| \geq |P_{2}| \geq \cdots \geq |P_{k}| }[/math]. The [math]\displaystyle{ k }[/math]-distance between [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] is the minimum [math]\displaystyle{ |P_{1}| }[/math] among all [math]\displaystyle{ {\mathcal P}_{k}(u,v) }[/math], and the [math]\displaystyle{ k }[/math]-diameter [math]\displaystyle{ d_{k}(G) }[/math] of [math]\displaystyle{ G }[/math] is

[math]\displaystyle{ d_{k}(G) = \max\{d_{k}(u,v): \; u \neq v\mbox{ and } u,v \in V(G). }[/math]

The concept of [math]\displaystyle{ k }[/math]-diameter naturally arises from the study of routing, reliability, randomized routing, fault tolerance and other communication protocols in the parallel architecture and distributed computer networks.