Locally k-connected graph

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

Locally [math]\displaystyle{ k }[/math]-connected graph --- локально [math]\displaystyle{ k }[/math]-связный граф.

Let [math]\displaystyle{ M }[/math] and [math]\displaystyle{ H }[/math] be two subgraphs of [math]\displaystyle{ G }[/math] with [math]\displaystyle{ V(H) \cap V(M) = \emptyset }[/math]. We say that [math]\displaystyle{ H }[/math] is locally [math]\displaystyle{ k }[/math]-connected to [math]\displaystyle{ M }[/math] in [math]\displaystyle{ G }[/math] if [math]\displaystyle{ G }[/math] contains [math]\displaystyle{ k }[/math] pairwise disjoint [math]\displaystyle{ (x,V(M)) }[/math] paths for every vertex [math]\displaystyle{ x \in H }[/math]. Let now [math]\displaystyle{ M }[/math] be a cycle in [math]\displaystyle{ G }[/math], and let [math]\displaystyle{ H }[/math] be a subgraph of [math]\displaystyle{ G - V(M) }[/math]. We say that [math]\displaystyle{ M }[/math] is locally longest with respect to [math]\displaystyle{ H }[/math] in [math]\displaystyle{ G }[/math] if we cannot obtain a cycle longer than [math]\displaystyle{ M }[/math] by replacing a segment [math]\displaystyle{ M[u,v] }[/math] by a [math]\displaystyle{ (u,v) }[/math]-path of [math]\displaystyle{ G }[/math] through [math]\displaystyle{ H }[/math].