In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

field of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, 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 In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...

, 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

C

, # there exists a homomorphism from

C

G

, and #

C

is minimal with this property. Two graphs are said to be homomorphism equivalent or hom-equivalent 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 ''K''₂. * By the Beckman–Quarles theorem, the infinite unit distance graph on all points of the

Euclidean plane In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...

or of any higher-dimensional

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...

is a core.

Properties

Every finite graph has a core, which is determined uniquely, up to

. 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 = 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 . Graph theory objects