Core (graph theory)

Quality 0.50 · 2 views · Updated 2 months ago

title: "Core (graph theory)" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["graph-theory-objects"] topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/Core_(graph_theory)" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::figure[src="https://upload.wikimedia.org/wikipedia/commons/0/02/Core_of_a_graph.svg" caption="The core C (in red) of the [[truncated tetrahedron]] graph G."] ::

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 C is a core if every homomorphism f:C \to C is an isomorphism, that is it is a bijection of vertices of C.

A core of a graph G is a graph C such that

There exists a homomorphism from G to C,
there exists a homomorphism from C to G, and
C is minimal with this property.

Two graphs are homomorphically equivalent if and only if they have isomorphic cores.

Examples

Any complete graph is a core.
A cycle of odd length is a core.
A graph G is a core if and only if the core of G is equal to G.
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.

Properties

Every finite graph has a core, which is determined uniquely, up to isomorphism. The core of a graph G is always an induced subgraph of G. If G \to H and H \to G then the graphs G and H are necessarily homomorphically equivalent.

Computational complexity

It is NP-complete to test whether a graph has a homomorphism to a proper subgraph, and co-NP-complete to test whether a graph is its own core (i.e. whether no such homomorphism exists) .

References

Godsil, Chris, and Royle, Gordon. Algebraic Graph Theory. Graduate Texts in Mathematics, Vol. 207. Springer-Verlag, New York, 2001. Chapter 6 section 2.
{{citation | last1 = Hell | first1 = Pavol | author1-link = Pavol Hell | last2 = Nešetřil | first2 = Jaroslav | author2-link = Jaroslav Nešetřil | doi = 10.1016/0012-365X(92)90282-K | issue = 1-3 | journal = Discrete Mathematics | mr = 1192374 | pages = 117–126 | title = The core of a graph | volume = 109 | year = 1992| doi-access = free
{{citation | last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil | last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez | contribution = Proposition 3.5 | doi = 10.1007/978-3-642-27875-4 | isbn = 978-3-642-27874-7 | location = Heidelberg | mr = 2920058 | page = 43 | publisher = Springer | series = Algorithms and Combinatorics | title = Sparsity: Graphs, Structures, and Algorithms | volume = 28 | year = 2012 }}.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::