Core — ядро.
1. Given a graph , a core of is a subgraph of such that is homomorphic to , but fails to be homomorphic to any proper subgraph of . This notion of a core is due to Hell and Nešetřil (1992). A graph is a core if is a core for itself. It is known, that in general, the problem of deciding whether is a core is NP-complete, but there exists a polinomial time algorithm to decide if is a core for the particular case when has the independence number . Finally, it is known that "almost all graphs" are cores.
2. Let denote the family of all maximum stable sets. Then the core is defined as . Thus, the core is the set of vertices belonging to all maximum stable sets.
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.