Core (graph theory)

From Wikipedia, the free encyclopedia

In the mathematical field of graph theory, a core is a notion that describes behavior of a graph with respect to graph homomorphisms.

[edit] 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.

[edit] Examples

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

[edit] 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.
This combinatorics-related article is a stub. You can help Wikipedia by expanding it.