P4-Connected graph

[math]\displaystyle{ \,P_4 }[/math]-Connected graph — [math]\displaystyle{ \,P_{4} }[/math]-связный граф.

A graph [math]\displaystyle{ \,G = (V,E) }[/math] is [math]\displaystyle{ \,P_{4} }[/math]-connected graph if for every partition of [math]\displaystyle{ \,V }[/math] into nonempty disjoint sets [math]\displaystyle{ \,V_{1} }[/math] and [math]\displaystyle{ \,V_{2} }[/math], some chordless path on four vertices and three edges (i.e. [math]\displaystyle{ \,P_{4} }[/math]) contains vertices from both [math]\displaystyle{ \,V_{1} }[/math] and [math]\displaystyle{ \,V_{2} }[/math].

The concept of [math]\displaystyle{ \,P_{4} }[/math]-connectedness leads to a structure theorem for arbitrary graphs in terms of [math]\displaystyle{ \,P_{4} }[/math]-connected components and suggests, in a quite natural way, a tree representation unique up to isomorphism. The leaves of the resulting tree are [math]\displaystyle{ \,P_{4} }[/math]-connected components and weak vertices, that is, vertices belonging to no [math]\displaystyle{ \,P_{4} }[/math]-connected component. The structure theorem and the corresponding tree representation provide tools for the study of graphs with a simple [math]\displaystyle{ \,P_{4} }[/math]-structure, such as [math]\displaystyle{ \,P_{4} }[/math]-reducible, [math]\displaystyle{ \,P_{4} }[/math]-extendible, [math]\displaystyle{ \,P_{4} }[/math]-sparse graphs.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.