Core (graph theory)

This article is about graph homomorphisms. For the subgraph in which all vertices have high degree, see k-core.

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 G is a core if every homomorphism $f:G \to G$ is an isomorphism, that is it is a bijection of vertices of G.
• A core of a graph H is a graph G such that

1. There exists a homomorphism from H to G,
2. there exists a homomorphism from G to H, and
3. G is minimal with this property.

Examples

• Any complete graph is a core.
• A cycle of odd length is a core.
• A core of a cycle of even length is K₂.

Properties

• Core of a graph is determined uniquely, up to isomorphism.
• If $G \to H$ and $H \to G$ then the graphs G and H have isomorphic cores.

See also

• the k-core of a graph, obtained by iteratively removing all vertices of degree at most k, is a different notion.

References

• Godsil, Chris, and Royle, Gordon. Algebraic Graph Theory. Graduate Texts in Mathematics, Vol. 207. Springer-Verlag, New York, 2001. Chapter 6 section 2.