Split graph

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

Split graph --- расщепляемый граф, граф расщеплений.

Split graph is a graph [math]\displaystyle{ (G,A,B) }[/math] for which there exists a partition of the vertex set into a clique [math]\displaystyle{ G(A) }[/math] and a stable set [math]\displaystyle{ G(B) }[/math]. If the clique and the stable set both have the same number of vertices [math]\displaystyle{ k }[/math], this graph is called a [math]\displaystyle{ k }[/math]-sun.

The split graphs were introduced independently by Foldes and Hammer (1976 -- 1977) and R.Tyshkevich (1980) (as polar graphs).