Core

Core — ядро.

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

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

Литература

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