Core (graph theory)
In the mathematical field of graph theory, a core is a notion that describes behavior of a graph with respect to graph homomorphisms.
Definition
Graph is a core if every homomorphism is an isomorphism, that is it is a bijection of vertices of.A core of a graph is a graph such that
- There exists a homomorphism from to,
- there exists a homomorphism from to, and
- is minimal with this property.
Examples
- Any complete graph is a core.
- A cycle of odd length is a core.
- A graph is a core if and only if the core of is equal to.
- Every two cycles of even length, and more generally every two bipartite graphs are hom-equivalent. The core of each of these graphs is the two-vertex complete graph K2.
- By the Beckman–Quarles theorem, the infinite unit distance graph on all points of the Euclidean plane or of any higher-dimensional Euclidean space is a core.