In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a core is a notion that describes behavior of a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

with respect to

graph homomorphism In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent verti ...

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 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 them. The word is ...

, 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 In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

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 graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

s are hom-equivalent. The core of each of these graphs is the two-vertex complete graph ''K''₂. * By the

Beckman–Quarles theorem In geometry, the Beckman–Quarles theorem, named after Frank S. Beckman and Donald A. Quarles Jr., states that if a transformation of the Euclidean plane or a higher-dimensional Euclidean space preserves unit distances, then it preserves all ...

, the infinite

unit distance graph In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graph ...

on all points of the

Euclidean plane In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...

or of any higher-dimensional

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

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 In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

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 In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

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