Semigirth

Материал из WikiGrapp

Semigirth --- полуобхват.

Let [math]\displaystyle{ G }[/math] be a (di)graph with its diameter [math]\displaystyle{ D }[/math] and the minimum degree [math]\displaystyle{ \delta }[/math], and let [math]\displaystyle{ \pi \geq 0 }[/math] be an integer. The [math]\displaystyle{ \pi }[/math]-semigirth [math]\displaystyle{ \ell^{\pi} = \ell^{\pi}(G), \; 1 \leq \ell^{\pi} \leq D }[/math], is defined as the greatest integer such that, for any two vertices [math]\displaystyle{ u,v }[/math],

a) if [math]\displaystyle{ d(u,v) \lt \ell^{\pi} }[/math], the shortest [math]\displaystyle{ u \rightarrow v }[/math] path is unique and there are at most [math]\displaystyle{ \pi }[/math] paths [math]\displaystyle{ u \rightarrow v }[/math] of length [math]\displaystyle{ d(u,v) + 1 }[/math],

b) if [math]\displaystyle{ d(u,v) = \ell^{pi} }[/math], there is only one shortest [math]\displaystyle{ u \rightarrow v }[/math] path.

The 0-semigirth [math]\displaystyle{ \ell^{0} = \ell }[/math] is simply called a semigirth. Observe that if [math]\displaystyle{ G }[/math] is a graph with girth [math]\displaystyle{ g }[/math], then the semigirth [math]\displaystyle{ \ell = \lfloor (g-1)/2 \rfloor }[/math].