K-Binding number

[math]\displaystyle{ k }[/math]-Binding number — [math]\displaystyle{ \,k }[/math]-связывающее число.

The [math]\displaystyle{ \,k }[/math]-binding number of [math]\displaystyle{ \,G }[/math] is defined to be

[math]\displaystyle{ bind^{k}(G) = \min_{X \in \delta^{k-1}(G)} \left\{\frac{|\Gamma^{k-1}(X)|}{|X|}\right\}, }[/math]

where

[math]\displaystyle{ \delta^{k}(G) = \{X: \; \emptyset \neq X \subseteq V(G)\mbox{ and } \Gamma^{k}(X) \neq V(G)\}. }[/math]

Let [math]\displaystyle{ k \geq 2 }[/math]. The following two properties are obvious.

1. Let [math]\displaystyle{ \,G }[/math] be a graph with [math]\displaystyle{ \,n }[/math] vertices. If [math]\displaystyle{ diam(G) \leq k-1 }[/math], then [math]\displaystyle{ \,bind^{k}(G) = n-1 }[/math].

2. If a graph [math]\displaystyle{ \,G }[/math] has at least one isolated vertex, then [math]\displaystyle{ \,bind^{k}(G) = 0 }[/math].

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.