Core

Core — ядро.

1. Given a graph [math]\displaystyle{ \,G }[/math], a core of [math]\displaystyle{ \,G }[/math] is a subgraph [math]\displaystyle{ \,C }[/math] of [math]\displaystyle{ \,G }[/math] such that [math]\displaystyle{ \,G }[/math] is homomorphic to [math]\displaystyle{ \,C }[/math], but [math]\displaystyle{ \,C }[/math] fails to be homomorphic to any proper subgraph of [math]\displaystyle{ \,G }[/math]. This notion of a core is due to Hell and Nešetřil (1992). A graph [math]\displaystyle{ \,G }[/math] is a core if [math]\displaystyle{ \,G }[/math] is a core for itself. It is known, that in general, the problem of deciding whether [math]\displaystyle{ \,G }[/math] is a core is NP-complete, but there exists a polinomial time algorithm to decide if [math]\displaystyle{ \,G }[/math] is a core for the particular case when [math]\displaystyle{ \,G }[/math] has the independence number [math]\displaystyle{ \,\alpha(G) \leq 2 }[/math]. Finally, it is known that "almost all graphs" are cores.

2. Let [math]\displaystyle{ \,\Omega(G) }[/math] denote the family of all maximum stable sets. Then the core is defined as [math]\displaystyle{ \,core(G) = \cap \{S: \; S \in\Omega(G)\} }[/math]. Thus, the core is the set of vertices belonging to all maximum stable sets.

Литература

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