Induced path number: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Induced path number''' --- число порождённых путей. The '''induced path number''' <math>\rho(G)</math> of a graph <math>G</math> is defined…») |
(нет различий)
|
Текущая версия от 15:46, 19 мая 2011
Induced path number --- число порождённых путей.
The induced path number [math]\displaystyle{ \rho(G) }[/math] of a graph [math]\displaystyle{ G }[/math] is defined as the minimum number of subsets into which the vertex set [math]\displaystyle{ V(G) }[/math] of [math]\displaystyle{ G }[/math] can be partitioned such that each subset induces a path.
If [math]\displaystyle{ G }[/math] is a graph such that [math]\displaystyle{ \rho(G) = k }[/math] and [math]\displaystyle{ \rho(G - v) = k - 1 }[/math] for every [math]\displaystyle{ v \in V(G) }[/math], then we say that [math]\displaystyle{ G }[/math] is [math]\displaystyle{ k }[/math]-minus-critical.