K-Binding number

Материал из WEGA
Перейти к навигации Перейти к поиску

[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].