K-Binding number: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''<math>k</math>-Binding number''' --- <math>k</math>-связывающее число. The '''<math>k</math>-binding number''' of <math>G</math> is defined to b…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>k</math>-Binding number''' - | '''<math>k</math>-Binding number''' — ''[[k-Связывающее число|<math>\,k</math>-связывающее число]].'' | ||
The '''<math>k</math>-binding number''' of <math>G</math> is defined to be | The '''<math>\,k</math>-binding number''' of <math>\,G</math> is defined to be | ||
<math>bind^{k}(G) = \min_{X \in \delta^{k-1}(G)} | <math>bind^{k}(G) = \min_{X \in \delta^{k-1}(G)} | ||
| Строка 13: | Строка 13: | ||
Let <math>k \geq 2</math>. The following two properties are obvious. | Let <math>k \geq 2</math>. The following two properties are obvious. | ||
1. Let <math>G</math> be a graph with <math>n</math> vertices. If <math>diam(G) \leq k-1</math>, then | 1. Let <math>\,G</math> be a [[graph, undirected graph, nonoriented graph|graph]] with <math>\,n</math> [[vertex|vertices]]. If <math>diam(G) \leq k-1</math>, then | ||
<math>bind^{k}(G) = n-1</math>. | <math>\,bind^{k}(G) = n-1</math>. | ||
2. If a graph <math>G</math> has at least one isolated vertex, then <math>bind^{k}(G) | 2. If a graph <math>\,G</math> has at least one [[isolated vertex]], then <math>\,bind^{k}(G) | ||
= 0</math>. | = 0</math>. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 17:46, 21 февраля 2012
[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.