F-Dominating cycle

Материал из WikiGrapp

[math]\displaystyle{ f }[/math]-Dominating cycle --- [math]\displaystyle{ f }[/math]-доминирующий цикл.

Let [math]\displaystyle{ f }[/math] be a non-negative integer-valued function defined on [math]\displaystyle{ V(G) }[/math]. Then a cycle [math]\displaystyle{ C }[/math] is called an [math]\displaystyle{ f }[/math]-dominating cycle if [math]\displaystyle{ d_{G}(C) \leq f(v) }[/math] for every [math]\displaystyle{ x \in V(G) }[/math]. By taking an appropriate function as [math]\displaystyle{ f }[/math], we can give a unified view to many cycle-related problems. If [math]\displaystyle{ f }[/math] is a constant function taking the value 0 (resp. 1), then an [math]\displaystyle{ f }[/math]-dominating cycle is a Hamiltonian cycle (resp. a dominating cycle) of [math]\displaystyle{ G }[/math].