Decomposable graph

Материал из WEGA

Decomposable graph --- разложимый граф.

We write [math]\displaystyle{ G = H_{1} \oplus H_{2} }[/math] if [math]\displaystyle{ G }[/math] is the edge disjoint union of its subgraphs [math]\displaystyle{ H_{1} }[/math] and [math]\displaystyle{ H_{2} }[/math]. If [math]\displaystyle{ G = H_{1} \oplus \cdots \oplus H_{k} }[/math], where [math]\displaystyle{ H_{1}, \ldots, H_{k} }[/math] are all isomorphic to [math]\displaystyle{ H }[/math], then [math]\displaystyle{ G }[/math] can be decomposed into subgraphs isomorphic to [math]\displaystyle{ H }[/math]; we say that [math]\displaystyle{ G }[/math] is [math]\displaystyle{ H }[/math]-decomposable and that [math]\displaystyle{ \{H_{1}, \ldots, H_{k}\} }[/math] is [math]\displaystyle{ H }[/math]-decomposition of [math]\displaystyle{ G }[/math]. In particular, [math]\displaystyle{ G }[/math] is [math]\displaystyle{ C_{m} }[/math]-decomposable if it can be decomposed into subgraphs isomorphic to an [math]\displaystyle{ m }[/math]-cycle.