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
is a core if every homomorphism
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
.
A core of a graph
is a graph
such that
# There exists a homomorphism from
to
,
# there exists a homomorphism from
to
, and
#
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
is a core if and only if the core of
is equal to
.
* 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''
2.
* 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
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 ...
. The core of a graph ''G'' is always an
induced subgraph of ''G''. If
and
then the graphs
and
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