P4-Connected graph

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

\,P_4-Connected graph\,P_{4}-связный граф.

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

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

Литература

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