Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 6 (2013) 323–350
Relations between graphs
Jan Hubička
Computer Science Institute of Charles University, Univerzita Karlova v Praze
Malostranské nám. 25, 118 00 Praha 1, Czech Republic
Jürgen Jost
Max Planck Institute for Mathematics in the Sciences
Inselstrasse 22, D-04103 Leipzig, Germany
Department of Mathematics, University of Leipzig, D-04081 Leipzig, Germany
Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM 87501, USA
Yangjing Long
Max Planck Institute for Mathematics in the Sciences
Inselstrasse 22, D-04103 Leipzig, Germany
Peter F. Stadler
Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for
Bioinformatics, University of Leipzig, Härtelstraße 16-18, D-04107 Leipzig, Germany
Max Planck Institute for Mathematics in the Sciences
Inselstrasse 22, D-04103 Leipzig, Germany
Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM 87501, USA
Fraunhofer Institut für Zelltherapie und Immunologie – IZI
Perlickstraße 1, D-04103 Leipzig, Germany
Department of Theoretical Chemistry, University of Vienna
Währingerstraße 17, A-1090 Wien, Austria
Center for non-coding RNA in Technology and Health
University of Copenhagen, Grønnegårdsvej 3, DK-1870 Frederiksberg C, Denmark
Ling Yang
School of Mathematical Sciences, Fudan University
No. 220 Handan Rd., 200433, Shanghai, China
Received 18 May 2012, accepted 24 October 2012, published online 14 January 2013
E-mail addresses: Jan.Hubicka@mff.cuni.cz (Jan Hubička), jost@mis.mpg.de (Jürgen Jost),
ylong@mis.mpg.de (Yangjing Long), studla@bioinf.uni-leipzig.de (Peter F. Stadler), yanglingfd@fudan.edu.cn
(Ling Yang)
Copyright c© 2013 DMFA Slovenije
324 Ars Math. Contemp. 6 (2013) 323–350
Abstract
Given two graphs G = (VG, EG) and H = (VH , EH), we ask under which conditions
there is a relation R ⊆ VG × VH that generates the edges of H given the structure of the
graph G. This construction can be seen as a form of multihomomorphism. It generalizes
surjective homomorphisms of graphs and naturally leads to notions of R-retractions, R-
cores, and R-cocores of graphs. Both R-cores and R-cocores of graphs are unique up to
isomorphism and can be computed in polynomial time.
Keywords: Generalized surjective graph homomorphism, R-reduced graph, R-retraction, binary re-
lation, multihomomorphism, R-core, cocore.
Math. Subj. Class.: 05C60, 05C76
1 Introduction
1.1 Motivation
Graphs are frequently employed to model natural or artificial systems [3, 11]. In many
applications separate graph models have been constructed for distinct, but at least concep-
tually related systems. One might think, e.g., of traffic networks for different means of
transportation (air, ship, road, railroad, bus). In the life sciences, elaborate network models
are considered for gene expression and the metabolic pathways regulated by these genes,
or for the co-occurrence of protein domains within proteins and the physical interactions of
proteins among each other.
Let us consider an example. Most proteins contain several functional domains, that
is, parts with well-characterized sequence and structure features that can be understood as
functional units. Protein domains for instance mediate the catalytic activity of an enzyme
and they are responsible for specific binding to small molecules, nucleic acids, or other
proteins. Databases such as SuperFamily compile the domain composition of a large
number of proteins. We can think of these data as a relation R ⊂ D × P between the set
D of domains and the set of P proteins which contain them. Protein-protein interaction
networks (PPIs) have been empirically determined for several species and are among the
best-studied biological networks [16]. From this graph, which has P as its vertex set, and
the relation R we can obtain a new graph whose vertex set are the protein domains D, with
edges connecting domains that are found in physically interacting proteins. This “domain
interaction graph” conveys information e.g. on the functional versatility of protein com-
plexes. On the other hand, we can use R to construct the domain-cooccurrence networks
(DCNs) [14] as simple relational composition R ◦R+. In examples like these, the detailed
connections between the various graphs have remained unexplored. In fact, there may not
be a meaningful connection between some of them, e.g. between PPIs and DCNs, while
in other cases there is a close connection: the domain interaction graph, for example, is
determined by the PPI and R.
A second setting in which graph structures are clearly related to each other is coarse-
graining. Here, sets of vertices are connected to a single coarse-grained vertex, with coarse-
grained edges inherited from the original graph. In the simplest case, we deal with quotient
graphs [15], although other, less stringent constructions are conceivable. Similarly, we
would expect that networks that are related by some evolutionary process retain some sort
J. Hubička et al.: Relations between graphs 325
p1 p2
p3p4
d1 d2 d3 d4
d1
d2
d3
d4
p1
p2
p3
p4
Graph G Relation R Graph G ∗R
Figure 1: The graph G ∗R is determined by the graph G and the relation R.
of structural relationship.
1.2 Main definitions
A well-defined mathematical problem is hidden in this setting: Given two networks, can we
identify whether they are related in meaningful ways? The usual mathematical approach to
this question, namely to ask for the existence of structure-preserving maps, appears to be
much too restrictive. Instead, we set out here to ask if there is a relation between the two
networks that preserves structures in a less restrained sense.
The idea is to transfer edges from a graph G to a graph H with the help of a relation
R between the vertex set V of G and the vertex set B of H . In this context, R is simply a
set of pairs (v, b), with v ∈ V, b ∈ B. Since graphs can be regarded as representations of
binary relations, we can also consider G as a relation on its vertex set, with (x, y) ∈ G if
and only if x and y are connected by an edge of G. We then have the composition G ◦ R
given by all pairs (x, b) for which there exists a vertex y ∈ V connected by an edge of G
to x and (y, b) ∈ R. This, however, like R is a relation between elements of different sets.
In order to equip the target set B with a graph structure, we simply connect elements u and
v in B if they stand in relation to connected elements of G. In the following, we give a
formal definition, and we shall then relate it to the composition of relations just described.
A directed graph G is a pair G = (VG, EG) such that EG is a subset of VG × VG. We
denote by VG the set of vertices of G and by EG the set of edges of G. We consider only
finite graphs and allow loops on vertices.
An undirected graph (or simply a graph)G is any directed graph such that (u, v) ∈ EG
if and only if (v, u) ∈ EG. We thus consider undirected graphs to be special case of
directed graphs and we still allow loops on vertices. A simple graph is an undirected graph
without loops.
Definition 1.1. Let G = (VG, EG) be a graph, B a finite set, and R ⊆ V × B a binary
relation, where for every element b ∈ B, we can find an element v ∈ VG such that (v, b) ∈
R. Then the graph G ∗R has vertex set B and edge set
EG∗R = {(u, v) ∈ B ×B| there is (x, y) ∈ EG and (x, u), (y, v) ∈ R} . (1.1)
An example of the ∗ operation is depicted in Fig. 1.
Graphs with loops are not always a natural model, however, so that it may appear more
appealing to consider the slightly modified definition.
326 Ars Math. Contemp. 6 (2013) 323–350
Definition 1.2. Let G = (VG, EG) be a simple graph, B a finite set, R a binary relation,
where for every element b ∈ B, we can find an element v ∈ VG such that (v, b) ∈ R. Then
the (simple) graph G ? R has vertex set B and edge set
EG?R = {(u, v) ∈ B ×B|u 6= v and there is (x, y) ∈ EG and (x, u), (y, v) ∈ R} .
(1.2)
We shall remark that these definitions remain meaningful for directed graphs, weighted
graphs (where the weight of edge is a sum of weights of its pre-images) as well as relational
structures. For simplicity, we restrict ourselves to undirected graphs (with loops). Most of
the results can be directly generalized.
Graphs can be regarded as representations of symmetric binary relations. Using the
same symbol for the graph and the relation it represents, we may re-interpret definition 1.1
as a conjugation of relations. R+ is the transpose of R, i.e., (u, x) ∈ R+ if and only if
(x, u) ∈ R. The double composition R+ ◦G ◦ R contains the pair (u, v) in B × B if and
only if there are x and y such that (u, x) ∈ R+, (y, v) ∈ R, and (x, y) ∈ EG. Thus
G ∗R = R+ ◦G ◦R. (1.3)
Simple graphs, analogously, correspond to the irreflexive symmetric relations. For any
relation R, let Rι denote its irreflexive part, also known as the reflexive reduction of R.
Since definition 1.2 explicitly excludes the diagonals, it can be written in the form
G ? R = (R+ ◦G ◦R)ι. (1.4)
We have G ? R = (G ∗ R)ι, and hence EG?R ⊆ EG∗R. The composition G ∗ R is of
particular interest when G is also a simple graph, i.e., G = Gι.
The main part of this contribution will be concerned with the solutions of the equation
G ∗ R = H . The weak version, G ? R = H , will turn out to have much less convenient
properties, and will be discussed only briefly in section 7.
Throughout this paper we use the following standard notations and terms.
For relation R ⊆ X × Y we define by R(x) = {p ∈ Y |(x, p) ∈ R} the image of x
under R and R−1(p) = {x ∈ X|(x, p) ∈ R} the pre-image of p under R.
The domain of R is defined by domR = {x ∈ X|∃p ∈ Y s.t. (x, p) ∈ R}, and the
image of R is defined by imgR = {p ∈ Y |∃x ∈ X s.t. (x, p) ∈ R}. We say that the
domain of R is full if for any x ∈ X we have R(x) 6= ∅. Analogously, the image is full if
for any p ∈ Y we have R−1(p) 6= ∅.
Let R ⊆ X × Y is a binary relation, then R is injective, if for all x and z in X and y in
Y it holds that if (x, y) ∈ R and (z, y) ∈ R then x = z. R is functional, if for all x in X ,
and y and z in Y it holds that if (x, y) ∈ R and (x, z) ∈ R then y = z.
We denote by IG the identity map on G, i.e., {(x, x)|x ∈ VG}.
Let G = (VG, EG) be a graph and let W ⊆ VG. The induced subgraph G[W ] has
vertex set W and (x, y) is an edge of G[W ] if x, y ∈W and (x, y) ∈ EG.
A graph Pk is a path of length k. Similarly, Ck is an (elementary) cycle of length k with
vertex set {0, 1, . . . , k − 1}. Finally, Kk is the complete (loopless) graph with k vertices.
An isolated vertex is a vertex with degree 0. Note that the vertex with a loop is not
isolated in this sense.
J. Hubička et al.: Relations between graphs 327
1.3 Matrix multiplication
The operation ∗ can also be formulated in terms of matrix multiplication. To see this,
consider the following variant of the operation on weighted graphs.
Definition 1.3. If G is a weighted graph, we use w(x, y) to denote the weight between x
and y. Given a finite setB and a binary relationR ⊆ VG×B,G~R is defined as a weighted
graph H with vertex set B, for any u, v ∈ B, w(u, v) =∑(x,u)∈R,(y,v)∈R w(x, y).
Ignoring the weights, operations ∗ and ~ are equivalent.
Using the language of matrices,G~R = H can be interpreted as matrix multiplication:
WG~R = R+WGR (1.5)
where R is the matrix representation of the relation R, i.e., Rxu = 1 if and only if (x, u) ∈
R, otherwise Rxu = 0, R+ denotes the transpose of R, and WG is the matrix of edge
weights of G.
1.4 Graph homomorphisms and multihomomorphisms
The notion of relations between graphs is in many ways similar (but not equivalent) to the
well studied notion of graph homomorphisms. The majority of our results focus on similar-
ities and differences between those two concepts. We give here only the basic definitions
of graph homomorphisms. For more details see [7].
A homomorphism from a graph G to a graph H is a mapping f : VG → VH such
that for every edge (x, y) of G, (f(x), f(y)) is an edge of H . Note that homomorphisms
require loops in H whenever (x, y) ∈ EG and f(x) = f(y). In contrast, f is a weak ho-
momorphism if (x, y) ∈ EG implies that either f(x) = f(y) or (f(x), f(y)) ∈ EH . Every
homomorphism from G to H induces also a weak homomorphism, but not conversely [9].
Since every homomorphism preserves adjacency, it naturally defines a mapping f1 :
EG → EH by setting f1((x, y)) = (f(x), f(y)) for all (x, y) ∈ EG. If f is surjective, we
call f a vertex surjective homomorphism, and if f1 is surjective, we call f an edge surjective
homomorphism. f is surjective homomorphism if it is both vertex- and edge-surjective [7].
A map f : VG → VH is, of course, a special case of a relation. This is seen by setting
F = {(x, f(x))|x ∈ VG}. Hence, there is a surjective homomorphism from G to H if and
only if there is a functional relation F such that G∗F = H . Another important connection
to the graph homomorphisms is the following simple lemma.
Lemma 1.4. If G ∗R = H , and the domain of R is full, then there is a homomorphism f
from G to H contained in R.
Proof. If G ∗R = H , then take any functional relation f ⊆ R, we have G ∗ f ⊆ H , where
f is a homomorphism from G to H .
Analogously, there is a weak surjective homomorphism fromG toH if and only if there
is a functional relation F such that G ? F = H , and there is a weak homomorphism from
G to H if there is a functional relation F ⊆ VG × VH such that G ? F is a subgraph of
H . The existence of relations between graphs thus can be seen as a proper generalization
of graph homomorphisms or weak graph homomorphisms, respectively.
328 Ars Math. Contemp. 6 (2013) 323–350
Finally, a full homomorphism from a graph G to a graph H is a vertex mapping f
such that for distinct vertices u and v of G, we have (u, v) an edge of G if and only if
(f(u), f(v)) is an edge of H , see [4].
Relation between graphs can be regarded also as a variant of multihomomorphisms.
Multihomomorphisms are building blocks of Hom-complexes, introduced by Lovász, and
are related to recent exciting developments in topological combinatorics [10], in particular
to deep results involved in proof of the Lovász hypothesis [1].
A multihomomorphism G → H is a mapping f : VG → 2VH \ {∅} (i.e., associating a
nonempty subset of vertices of H with every vertex of G) such that whenever {u1, u2} is
an edge of G, we have (v1, v2) ∈ EH for every v1 ∈ f(u1) and every v2 ∈ f(u2).
The functions from vertices to sets can be seen as representation of relations. A relation
with full domain thus can be regarded as surjective multihomomorphism, a multihomomor-
phism such that pre-image of every vertex in H is non-empty and for every edge (u, v) in
H we can find an edge (x, y) in G satisfying u ∈ f(x), v ∈ f(y).
1.5 Examples
Similarly to graph homomorphisms, the equation G ∗ R = H (or G ? R = H respec-
tively) may have multiple solutions for some pairs of graphs (G,H), while there may be
no solution at all for other pairs.
As an example, consider K2 (two vertices x, y connected by an edge) and C3 (a cycle
of three vertices u, v, w). Denote R1 = {(u, x), (v, y)}, R2 = {(v, x), (w, y)}, R3 =
{(w, x), (u, y)}, then it is easily seen that C3 ∗ Ri = K2 for each 1 ≤ i ≤ 3, i.e. the
equation C3 ∗R = K2 has more than one solution.
On the other hand, there is no relation R such that K2 ∗ R = C3. Otherwise, each
vertex of C3 is related to at most one vertex of K2, since C3 is loop free; hence there exists
a vertex in K2 which has no relation to at least two vertices in C3, w.l.o.g., one can assume
(x, u), (x, v) /∈ R; then the definition of ∗ implies that there is no edge between u and v,
which causes a contradiction.
Because relations do not need to have full domain (unlike graph homomorphisms),
there is always an relation from a graph G to its induced subgraph G[W ].
Relations with full domain are not restricted to surjective homomorphisms. As a simple
example, consider paths P1 with vertex set {x, y} and P2 with vertex set {u, v, w}, respec-
tively, and set R = {(x, u), (x,w), (y, v)}. One can easily verify P1 ∗ R = P2 by direct
computation. Here, R is not functional since x has two images.
1.6 Outline and main results
This paper is organized as follows.
In section 2 the basic properties of the strong relations between graphs are compiled.
It is shown that relations compose and every relation can be decomposed in a standard
way into a surjective and an injective relation (Corollary 2.3). We discuss some structural
properties of graph preserved by the relations.
Equivalence on the class of graphs induced by the existence of relations between graphs
is the topic of section 3. We consider two forms: the strong relational equivalence, where
relations are required to be reversible, and weak relational equivalence. Equivalence classes
of strong relational equivalence are characterized in Theorem 3.8. To describe equivalence
classes of the weak relational equivalence we introduce the notion of an R-core of a graph
J. Hubička et al.: Relations between graphs 329
and show that it is in many ways similar to the more familiar construction of the graph core
(Theorem 3.17). We explore in particular the differences between core and R-core and an
effective algorithm to compute the R-core of given graph is provided.
Section 4 is concerned with the partial order induced on relations between two fixed
graphs G and H . Focusing on the special case G = H the minimal elements of this partial
order are described. In Theorem 4.7 we give a, perhaps surprisingly simple, characteriza-
tion of those graphs G for which all relations of G to itself are automorphisms.
R-retraction is defined in section 5 in analogy to retractions. It naturally gives rise to a
notion of R-reduced graphs that we show to coincide with the concept of graph cores. By
reversing the direction of relations, however, we obtain the concept of a cocore of a graph,
which does not have a non-trivial counterpart in the world of ordinary graph homomor-
phisms, and explore its properties.
The computational complexity of testing for the existence of a relation between two
graphs is briefly discussed in section 6. In Theorem 6.1 we describe the reduction of this
problem to the surjective homomorphism problem.
Finally, in section 7 we briefly summarize the most important similarities and differ-
ences between weak and strong relational composition.
2 Basic properties
2.1 Composition
Recall that the composition of binary relations is associative, i.e., suppose R ⊆ W × X ,
S ⊆ X × Y , and T ⊆ Y × Z. Then R ◦ (S ◦ T ) = (R ◦ S) ◦ T . Furthermore, the
transposition of relations satisfies (R ◦ S)+ = S+ ◦ R+. Interpreting the graph G as a
relation on its vertex set, we easily derive the following identities:
Lemma 2.1 (Composition law). (G ∗R) ∗ S = G ∗ (R ◦ S).
Proof. (G ∗R) ∗ S = S+ ◦ (R+ ◦G ◦R) ◦ S = (S+ ◦R+) ◦G ◦ (R ◦ S)
= (R ◦ S)+ ◦G ◦ (R ◦ S) = G ∗ (R ◦ S).
Now we show that every relation R can be decomposed, in a standard way, to a relation
RD duplicating vertices and a relation RC contracting vertices.
Lemma 2.2. Let R ⊆ X × Y be a relation. Then there exists a subset A of X , a set B, an
injective relation with full domain RD ⊆ A × B and a functional relation RC ⊆ B × Y ,
such that R = IA ◦RD ◦RC , where IA is the identity on X restricted to A.
Proof. Put A = domR. Then the relation IA removes vertices in X \ domR. It remains
to show, therefore, that any relation R ⊆ X × Y with full domain can be decomposed into
an injective relation RD ⊆ X × B and a functional relation RC ⊆ B × Y . To see this,
set B = R and declare (x, α) ∈ RD if and only if α = (x, p) ∈ R for some p ∈ Y ,
and (β, q) ∈ RC if and only if β = (y, q) ∈ R for some y ∈ X . By construction RD
is injective and RC is functional. Furthermore, (x0, p0) ∈ RD ◦ RC if and only if there
is α ∈ R that is simultaneously of the form (x0, p) and (x, p0), i.e., x = x0 and p = p0.
Hence (x0, p0) ∈ R.
Note that this decomposition is not unique. For instance, we could construct B from
multiple copies of R. More precisely, let B = R × {1, 2, · · · , k}, then we would set(
x, (α, i)
)
∈ RD (1 ≤ i ≤ k) if and only if α = (x, p) ∈ R for some p ∈ Y , etc.
330 Ars Math. Contemp. 6 (2013) 323–350
The set B as constructed in the proof of Lemma 2.2 has minimal size. To see this, it
suffices to show that, givenB there is a mapping fromB ontoR. SinceRD is injective and
RC is functional we may set
α ∈ B 7→ (R−1D (α), RC(α)).
SinceR = IA ◦RD ◦RC we conclude that the mapping is surjective, and hence |B| ≥ |R|.
According to Lemma 2.1, the decomposition of R in Lemma 2.2 can be restated as
follows:
Corollary 2.3. Suppose G ∗ R = H . Then there is a set B, an injective relation RD ⊆
domR × B with full domain, and a surjective relation RC ⊆ B × imgR such that
G[domR] ∗RD ∗RC = H .
In diagram form, this is expressed as
G
RD ##
R=RD◦RC // H
G ∗RD
RC
;; (2.1)
We shall remark that from the fact the relations compose it follows that the existence of
a relation implies a quasi-order on graphs that is related to the homomorphism order. This
order is studied more deeply in [8].
2.2 Structural properties preserved by relations
In this subsection we investigate structural properties ofH that can be derived from knowl-
edge about certain properties of G and the fact that there is some relation R such that
G ∗R = H .
2.2.1 Connected components
Proposition 2.4. Let G∗R = H and denote by H1, · · · , Hk the connected components of
H . Then there are relations Ri ⊆ VG×VHi for each 1 ≤ i ≤ k such that G ∗Ri = Hi and
R =
⋃k
i=1Ri. Furthermore, set Gi = G[R
−1(VHi)]. Then there are no edges between Gi
and Gj for arbitrary i 6= j.
Proof. Define the restriction of R to the connected components of H as Ri = {(x, y) ∈
R|y ∈ VHi}. Clearly, R is the disjoint union of the Ri and G ∗Ri ⊆ Hi. The definition of
∗ implies H = G∗R = (⋃iRi)+ ◦G◦(⋃j Rj) = ⋃i⋃j R+i ◦G◦Rj . Since Ri and Rj
relate vertices of G to different connected components of H , we have R+i ◦G ◦Rj = ∅. It
follows thatH =
⋃
i
⋃
j R
+
i ◦G◦Rj =
⋃
iR
+
i ◦G◦Ri =
⋃
iG∗Ri. HenceG∗Ri = Hi.
Any edge between Gi and Gj would generate edges between Hi and Hj , thus causing
a contradiction to our assumptions.
Denote by b0(G) the number of connected components ofG, then from Proposition 2.4
we arrive at:
J. Hubička et al.: Relations between graphs 331
Corollary 2.5. Suppose both G and H do not have isolated vertices. If G ∗R = H and R
has full domain, then b0(G) ≥ b0(H).
Proof. Our notations is the same as in Proposition 2.4. We claim for arbitrary connected
component C of graph G, there exists a unique i, such that C is a connected component of
Gi. Otherwise one can find two vertices x, y ∈ C, x and y adjacent, such that x ∈ VGi
and y ∈ VGj , since G has no isolated vertices, which contradicts E(Gi, Gj) = ∅. Thus
b0(G) ≥ b0(H) is easily followed.
From corollary 2.5, we know that H is connected whenever G is connected. The con-
nectedness of G, however, cannot be deduced from the connectedness of H . For example,
consider G = P1 ∪ P1 with vertex set {x1, x2, x3, x4} and edges {x1, x2} and {x3, x4},
and H = P2 with vertex set {v1, v2, v3}. Set R = {(x1, v1), (x2, v2), (x3, v2), (x4, v3)}.
One can easily verify that G ∗ R = H . On the other hand, H is connected but G has 2
connected components. The point here is, of course, that R is not injective.
2.2.2 Colorings
Graph homomorphisms of simple graphs can be seen as generalizations of colorings: A
(vertex) k-coloring of G is a mapping c : VG → {1, 2, . . . , k} such that adjacent vertices
have distinct colors, i.e., c(u) 6= c(v) whenever (u, v) ∈ EG. Every k-coloring c can be
also seen as a homomorphism c : G→ Kk.
The chromatic number χ is defined as the minimal of colors needed for a coloring, see
e.g. [7]. Thus, if R is a functional relation describing a vertex coloring, then G ∗R ⊆ Kk.
Conversely, G ∗ R ⊆ Kk, where R has full domain, then from Lemma 1.4, there exists a
homomorphism from G to Kk, which is a coloring of G.
Lemma 2.6. If G is a simple graph and R has full domain, then χ(G) ≤ χ(G ∗R).
Proof. SupposeG∗R = H and the domain ofR is full, from Lemma 1.4 we knowG→ H ,
so χ(G) ≤ χ(G ∗R).
2.2.3 Distances
Observation 2.7. If Pk ∗R = G, G is a simple graph and the domain of R is full, Pk with
the vertex set 0, 1, · · · , k, then there is a walk [v0, v1, . . . , vk] in G, where (i, vi) ∈ R for
0 ≤ i ≤ k.
Observation 2.8. If Ck ∗ R = G, G is a simple graph and the domain of R is full, then
there is a closed walk [v0, v1, . . . , vk−1] in G, where (i, vi) ∈ R for 0 ≤ i ≤ k − 1.
Let dG(x, y) denote the canonical distance on graph G, i.e., dG(x, y) is the minimal
length of a path in graph G that connects vertices x and y; if there is no path connects
vertices x and y, then the distance is infinite.
Lemma 2.9. Suppose there exists a relationR with full domain s.t.G∗R = H , x, y ∈ VG,
u, v ∈ VH and (x, u) ∈ R, (y, v) ∈ R. If x 6= y, then dH(u, v) ≤ dG(x, y); If x = y and
x is not an isolated vertex, then dH(u, v) ≤ 2.
332 Ars Math. Contemp. 6 (2013) 323–350
Proof. If x = y and x is not isolated, pick a vertex z of graph G which is adjacent to
vertex x, and find a vertex w ∈ H satisfying (z, w) ∈ R. Then (w, u) ∈ EH and similarly
(w, v) ∈ EH . So dH(u, v) ≤ 2.
If x 6= y, choose the shortest path P = x, x1, x2, · · · , xk, y between x and y, and find
corresponding vertices u1, u2, · · · , uk ∈ H such that(xi, ui) ∈ R for any 1 ≤ i ≤ k − 1
it is easily seen that (u, u1) ∈ EH , (ui, ui+1) ∈ EH and (uk, v) ∈ EH , then d(u, v) ≤
d(x, y).
The eccentricity  of a vertex v is the greatest distance between v and any other vertex.
The radius of a graph G, denoted by rad(G), is the minimum eccentricity of any vertex.
The diameter of a graph G, denoted by diam(G), is the maximum eccentricity of any
vertex in the graph, i.e., the largest distance between any pair of vertices.
Corollary 2.10. Suppose G ∗ R = H , G and H are connected graphs, and R has full
domain, then rad(H) ≤ max{rad(G), 2}.
An analogous result holds for the diameters. In particular, if G is not a complete graph,
then diam(G) ≥ diam(G ∗R).
Corollary 2.11. There is a relation from the path of length k, Pk, to the path of length l,
Pl, if and only if either k ≥ l or k = 1, l = 2.
Proof. For k ≥ l there is a surjective homomorphism f from Pk to Pl and hence by Lemma
1.4 there is also a relation from Pk to Pl. In Section 1.5 we already showed a relation from
P1 to P2.
To show that P1 ∗R = P2 is the only case with k < l we first observe that Lemma 2.9
excludes the existence of relation from Pk to Pl for 1 < k < l. Now suppose R satisfies
P1 ∗R = Pk for k > 2. Since Pk has at least 4 vertices, either one of the vertices of P1 has
at least 3 images so that P1 ∗ R has a vertex with degree at least 3, or both of the vertices
in P1 have at least 2 images, in which case all vertices of P1 ∗R have degree at least 2. In
both cases P1 ∗R cannot be a path.
In particular, {P1, P2} is the only pair of paths such that there is a relation between
them in both directions.
2.2.4 Complete graphs
The complement graph H of a simple graph H has the same vertex set as H , and two
vertices are connected in H if and only if they are not connected in H .
Note that in this subsection we do not require that the domain of R is full.
Proposition 2.12. Let H be a simple graph. Then there exists a relation R such that
Kk ∗R = H if and only if H is the disjoint union of at most k complete graphs.
Proof. Denote the connected components of H by H1, . . . ,Hm. If m ≤ k and every
connected component of H is a complete graph, let R = {(i, u)|i = 1, · · · ,m, u ∈ VHi}
and by the definition of complement graph, for any i = 1, · · · ,m, all the vertices in Hi are
independent in H , and u is adjacent to v whenever u ∈ VHi and v ∈ VHj for distinct i, j.
Hence it is easily seen that Kk ∗R = H .
Conversely, if Kk ∗ R = H , denote the vertices in Kk by 1, · · · , k, s.t. domR =
{1, · · · ,m}. We claim that R is injective, otherwise H would have loops. Thus VH is
J. Hubička et al.: Relations between graphs 333
the disjoint union of R(1), · · · , R(m). For any two distinct vertices u, v in R(i), u and v
are independent in H and for distinct i and j every vertex in R(i) are adjacent with every
vertex in R(j) whenever R(i) 6= ∅. Therefore for any i, R(i) is the vertex set of a connect
component of H , which is a complete graph.
2.2.5 Subgraphs
Relations between graphs intuitively imply relations between local subgraphs. In this sec-
tion we make this concept more precise. Denote by
NG[x] := {z ∈ VG|z = x ∨ (x, z) ∈ EG} (2.2)
the closed neighborhood of x in G. Furthermore, we let NG[x] := VG \NG[x] be the set
of vertices that are not adjacent (or identical) to x in G and denote by Gx := G[NG[x]] the
induced subgraph of G that is obtained by removing the closed neighborhood of a vertex
x.
Analogously, for a subset S ⊆ VG we define
S = G
[
VG \
⋃
x∈S
NG[x]
]
(2.3)
as the induced subgraph obtained by removing all vertices in S and their neighbors.
Then we have the following result about relations between local subgraphs.
Proposition 2.13. SupposeG∗R = H and S andD are subsets of VG and VH , respectively,
such that G[S] ∗R|(S×D) = H[D], R|(S×D) has full domain on S, and there is no isolated
vertex in D. Then S ∗ R̃ = D, where R̃ = R|(S×D) is the corresponding restriction of R.
Proof. Obviously, S ∗ R̃ is an induced subgraph of D. We have to show the reverse inclu-
sion. Given u ∈ VD and x ∈ R−1(u), we first show that there are two possibilities:
1. x is a vertex of S.
2. x is an isolated vertex of S.
Assume that is not the case, i.e., that x /∈ VS and that x is either a non-isolated vertex of S
or x is in the neighborhood of some vertex of S. In either case there is y ∈ S connected by
an edge to x. Consequently there is also v ∈ D, such that v ∈ R(y), connected by an edge
to u. It follows u /∈ VD, a contradiction.
Now consider an arbitrary edge (u, v) ∈ ED. We have (x, y) ∈ EG such that u ∈ R(x)
and v ∈ R(y). It follows that x and y are not isolated and thus x, y are vertices of S.
Consequently S ∗ R̃ has precisely the same edges as D. Because D has no isolated vertices
and thus every vertex is an endpoint of some edge, we know that the vertex set of S ∗ R̃ is
same as the vertex set of D.
This result is of particular practical use in the special case where S and D consist of
a single vertex. When looking for a relation R such that G ∗ R = H one can remove a
vertex including its neighborhood from G as well as the prospective image including the
neighborhood from H and solve the problem on the subgraphs.
334 Ars Math. Contemp. 6 (2013) 323–350
3 Relational equivalence
Graphs G and H are homomorphism equivalent (or hom-equivalent) if there exists homo-
morphisms G → H and H → G. It is well known that every equivalence class of the
homomorphism order contains a minimal representative that is unique up to isomorphism:
the graph core [7].
We define similar equivalences implied by the existence of (special) relations between
graphs. In this section, we require all relations to have full domain unless explicitly stated
otherwise. With this condition we will show that these equivalences produce a rich structure
closely related to but distinct from the structure of homomorphism equivalences.
This may come as a surprise: the equivalence implied by the existence of surjective
homomorphisms is not interesting. Consider two graphs G and H and suppose there are
surjective homomorphisms f : G → H and g : H → G. Since every vertex in VG has
at most one image under f , we have |VG| ≥ |VH |. Analogously |VH | ≥ |VG|, and hence
|VG| = |VH |. Thus f and g are both bijective, and G is isomorphic to H .
3.1 Reversible relations
Definition 3.1. A relation R is reversible with respect to graph G if (G ∗R) ∗R+ = G.
We write NG(x) := {z ∈ VG|(x, z) ∈ EG} for the open neighborhood of vertex x in
graph G.
Proposition 3.2. Suppose R = RD ◦ RC , where RD and RC are constructed as in the
proof of Proposition 2.2. Then R is reversible with respect G if and only if for every α and
β satisfying RC(α) = RC(β) we have NG∗RD (α) = NG∗RD (β).
Proof. We set G1 = G ∗ RD, then from Lemma 2.1 we have G1 ∗ RC = H . If RC(α) =
RC(β) implies NG1(α) = NG1(β), then H ∗ R+C = G1. Since G1 ∗ R+D = H , we have
H ∗R+C ∗R+D = H ∗R+ = G, i.e., R is reversible.
Conversely, since R is reversible, i.e., H ∗ R+ = G, setting G2 = H ∗ R+C gives
G2∗R+D = G. HenceG1∗RC ∗R+C = G2 andG2∗R+D ∗RD = G1. From IG1 ⊆ RC ∗R+C
we conclude G1 ⊆ G2, and similarly IG2 ⊆ R+D ∗RD yields G1 ⊇ G2. Hence G1 = G2.
R+C is injective, hence α, β ∈ VG2 = VG1 has the same open neighborhood whenever the
pre-image of α and β under R+C coincide, i.e. RC(α) = RC(β).
RD is an injective relation, hence one can easily get NG∗RD (α) = RD(NG(x)) pro-
vided that (x, α) ∈ RD. On the other hand, if we define R to be the image of RD as in
the proof of Proposition 2.2, then RC(α) = RC(β) implies there are two distinct vertices
x, y ∈ VG, s.t. (x, u), (y, u) ∈ R, where u = RC(α) = RC(β), and verse visa. Using
Proposition 3.2 we thus obtain
Proposition 3.3. A relation R is reversible with respect to G if and only if for every two
vertices x and y such that R(x) ∩R(y) 6= ∅ we have NG(x) = NG(y).
3.2 Strong relational equivalence
Definition 3.4. Two graphs G and H are (strongly) relationally equivalent, G v H , if
there is a relation R such that G ∗R = H and H ∗R+ = G.
Lemma 3.5. Relational equivalence is an equivalence relation on graphs.
J. Hubička et al.: Relations between graphs 335
G H Gthin = Hthin
Figure 2: Non-isomorphic graphs G and H with isomorphic thin graphs.
Proof. The relation v is reflexive since G ∗ IG = G. Symmetry also follows directly
from the definition. Suppose G ∗ R = H and H ∗ R+ = G and H ∗ Q = K and
K ∗Q+ = H , i.e., (G ∗R) ∗Q = K and (K ∗Q+) ∗R+ = G, i.e., G ∗ (R ◦Q) = K and
K ∗ (Q+ ◦R+) = K ∗ (R ◦Q)+ = G, i.e., v is also transitive.
Definition 3.6. The thinness relation S of G is the equivalence relation on VG defined by
(x, y) ∈ S if and only if NG(x) = NG(y). A graph G is called thin if every vertex forms
its own class in S.
Thin graphs are also known as “point determining graphs” [13].
We denote by S the corresponding partition of VG, and write RS ⊆ VG × S for the
relation that associates each vertex with its S-equivalence class, i.e., (x, β) ∈ RS if and
only if x ∈ β.
Definition 3.7. The thin graph ofG, denoted byGthin, is the quotient graphG/S, i.e.,Gthin
has vertex set S and two equivalence classes σ and τ of S are adjacent in Gthin if and only
if (x, y) is an edge of G with x ∈ σ and y ∈ τ .
As noted e.g. in [6, p.81], Gthin is itself a thin graph. Furthermore, RS is a full homo-
morphism of G to Gthin, see [4].
Thinness and the quotients w.r.t. the thinness relation play an important role in particu-
lar in the context of product graphs, see [9]. In this context it is well known that G can be
reconstructed from Gthin and the knowledge of the S-equivalence classes. In fact, we have
Gthin ∗RS+ = G. (3.1)
Theorem 3.8. G and H are in the same equivalence class w.r.t. v if and only if their thin
graphs are isomorphic.
Proof. Assume G v H . From Equation(3.1) we know that G v Gthin, H v Hthin, so
Gthin v Hthin. Now we claim thatGthin andHthin are isomorphic. SupposeGthin∗R = Hthin,
then the pre-image ofR is unique. Otherwise, there exist distinct vertices x, y ∈ VGthin such
that R(x) = R(y), then NGthin(x) = NGthin(y), contradicting thinness. Likewise, the pre-
image of R−1 is unique, i.e., the image of R is unique. Hence R is one-to-one.
The example in Fig. 2 shows that thin graphs can be isomorphic while G and H them-
selves are not isomorphic. Relational equivalence thus is coarser than graph isomorphism
(surjective homomorphic equivalence) but stronger than homomorphic equivalence.
336 Ars Math. Contemp. 6 (2013) 323–350
1
23
4
5
6
7
1
2
4
5
6
7
Figure 3: G andH are weakly relationally equivalent but have non-isomorphic thin graphs.
3.3 Weak relational equivalence
Definition 3.9. Two graphs G and H are weak relationally equivalent, G vw H , if there
are relations R and S such that G ∗R = H and H ∗ S = G.
Lemma 3.10. Weak relational equivalence is an equivalence relation on graphs.
Proof. By definition vw is symmetric. Because G ∗ IG = G, relation vw is reflexive.
Suppose G vw G′ and G′ vw G′′. Thus there are relations R, S, R′, and S′, such that
G′ = G ∗ R, G′′ = G′ ∗ R′, G = G′ ∗ S, and G′ = G′′ ∗ S′. By the composition law
(Lemma 2.1) it follows that G′′ = G ∗ (R ◦ R′) and G = G′′ ∗ (S′ ◦ S), i.e, G vw G′′.
Hence vw is transitive.
Strong relational equivalence implies weak relational equivalence. To see this, simply
observe that the definition of the weak form is obtained from the strong one by setting
S = R+.
The converse is not true, as shown by the graphsG andH in Fig. 3: It is easy to see that
their thin graphs are different and thus G and H are not strongly relationally equivalent.
However, are relationally equivalent. To get relation from G to H contract vertices 2 and 3
and keep other vertices on place, i.e.,
R = {(1, 1), (2, 2), (3, 2), (4, 4), (5, 5), (6, 6), (7, 7)}.
To get relation from H to G, duplicate 5 and 7 and contract them together to 3,
S = {(1, 1), (2, 2), (4, 4), (5, 5), (6, 6), (7, 7), (5, 3), (7, 3)}.
Consequently, weak relational equivalence is coarser than strong relational equivalence.
3.4 R-cores
A graph is an R-core, if it is the smallest graph (in the number of vertices) in its equivalence
of vw.
This notion is analogous to the definition of graph cores. In this section we show
properties of R-cores that are similar to the properties of graph cores. To this end we first
need to develop a simple characterization of R-cores.
Again we start from a decomposition of relations. Consider a relation R such that
G ∗ R = H . We seek for pair of relations R1 and R2 such that R = R1 ◦ R2. In contrast
J. Hubička et al.: Relations between graphs 337
to Lemma 2.2, however, we now look for a decomposition so that the graph G′ = G ∗ R1
is smaller (in the number of vertices) than G.
G
R1   
R=R1◦R2 // H
G′
R2
>> (3.2)
The existence of such a decomposition follows from a translation of the well-known Hall
Marriage Theorem [12] to the language of relations. We say that the relation R ⊆ A × B
satisfies the Hall condition, if for every S ⊆ A we have |S| ≤ |R(S)|.
Theorem 3.11 (Hall’s theorem). If G ∗R = H and R satisfies the Hall condition, then R
contains a monomorphism f : G→ H .
Proof. The Hall Marriage Theorem is usually described on set systems. For set systems
satisfying the Hall condition, the theorem guarantees the existence of a system of distinct
representatives, see i.e. [12]. Relations can be seen as set systems (defined by the images
of individual vertices). Furthermore, in our setting the system of distinct representatives
directly corresponds to a monomorphism contained in the relation R.
Lemma 3.12. If G ∗R = H and relation R does not satisfy the Hall condition, then there
are relations R1 and R2 such that R = R1 ◦ R2, and the number of vertices of graph
G′ = G ∗R1 is strictly smaller than the number of vertices of G.
Proof. Without loss of generality assume that VG ∩ VH = ∅. If R does not satisfy the Hall
condition, then there exists a vertex set S ⊂ VG such that |S| > |R(S)|. Now we define
relations R1 and R2 as follows:
R1(x) =
{
R(x) for x ∈ S,
x otherwise,
R2(x) =
{
x for x ∈ R(S),
R(x) otherwise.
(3.3)
Obviously R1 ◦R2 = R and |VG′ | = |VG| − (|S| − |R(S)|) < |VG|.
This immediately gives a necessary, but in general not sufficient, condition for a graph
to be an R-core.
Corollary 3.13. If G is an R-core, then every relation R such that G ∗R = G satisfies the
Hall condition and thus contains a monomorphism.
Proof. Assume that there is a relation R that does not satisfy the Hall condition. Then
there is a graph G′, |VG′ | < |VG|, and relations R1 and R2 such that G ∗ R1 = G′ and
G′ ∗R2 = G. Consequently G′ is a smaller representative of the equivalence class of vw,
a contradiction with G being R-core.
To see that the condition of Corollary 3.13 is not sufficient consider a graph consisting
of two independent vertices.
Next we show that R-cores are, up to isomorphism, unique representatives of the equiv-
alence classes of vw.
338 Ars Math. Contemp. 6 (2013) 323–350
R1
R2
G
f
I ⊆ R′1
GR-core
Figure 4: Construction of an embedding from GR-core to G.
Proposition 3.14. If both G and H are R-cores in the same equivalence class of vw, then
G and H are isomorphic.
Proof. Because both G and H are R-cores, we know that |VG| = |VH |.
Consider relationsR1 andR2 such thatG∗R1 = H andH∗R2 = G. Applying Lemma
3.12 we know that R1 satisfies the Hall condition. Otherwise there would be a graph G′
with |VG′ | < |VG| so that G′ is relationally equivalent to both G and H contradicting
the fact that G and H are R-cores. Similarly, we can show that R2 also satisfies the Hall
condition.
From Theorem 3.11 we know that there is a monomorphism f from G to H , and
monomorphism g from H to G. It follows that number of edges of G is not larger than
the number of edges of H and vice versa. Because G and H have the same number of
edges and same number of vertices, G and H must be isomorphisms.
It thus makes sense to define a construction analogous to the core of a graph.
Definition 3.15. H is an R-core of graph G if H is an R-core and H vw G.
All R-cores of graph G are isomorphic as an immediate consequence of Prop. 3.14. We
denote the (up to isomorphism) unique R-core of graph G by GR-core.
Lemma 3.16. GR-core is isomorphic to a (not necessarily induced) subgraph of G.
Proof. Take any relationR such thatGR-core∗R = G. By the same argument as in Corollary
3.13, there is a monomorphism f : GR-core → G contained in R. Consider the image of f
on G.
Theorem 3.17. GR-core is isomorphic to an induced subgraph of G.
Proof. Fix R1 and R2 such that GR-core ∗R1 = G and G ∗R2 = GR-core.
R = R1◦R2 is a relation such thatGR-core∗R = GR-core. By Corollary 3.13,R contains
a monomorphism f : GR-core → GR-core. Because such a monomorphism is a permutation,
there exists n such that fn, the n-fold composition of f with itself, is the identity.
J. Hubička et al.: Relations between graphs 339
Put R′1 = R
n−1 ◦R1. Because Rn contains the identity and Rn = R′1 ◦R2, it follows
that for every x ∈ VGR-core , there is a vertex I(x) ∈ VG such that I(x) ∈ R′1(x) and
x ∈ R2(I(x)).
We show that for two vertices x 6= y, we have I(x) 6= I(y) and thus both I and I−1
are monomorphisms. Assume, that is not the case, i.e., that there are two vertices x 6= y
such that I(x) = I(y). Consider an arbitrary vertex z in the neighborhood of x. It follows
that I(z) must be in the neighborhood of I(x) and consequently z is in the neighborhood
of y. Thus the neighborhoods of x and y are the same. By Theorem 3.8, however, we know
that the R-core is a thin graph (because weak relational equivalence is coarser than strong
relational equivalence), a contradiction.
Finally observe that I is an embedding from GR-core to G. For every edge (x, y) ∈
EGR-core we also have edge (I(x), I(y)) ∈ EG because I is contained in relation R′1. Sim-
ilarly because I−1 is contained in relation R2, every edge (I(x), I(y)) ∈ EG corresponds
to an edge (x, y) ∈ EGR-core .
We close the section with an algorithm computing the R-core of a graph. In contrast
to graph cores, where the computation is known to be NP-complete, there is a simple
polynomial algorithm for R-cores.
Observe that the R-core of a graph containing isolated vertices is isomorphic to the
disjoint union of the R-core of the same graph with the isolated vertices removed and a
single isolated vertex. The R-core of a graph without isolated vertices can be computed by
Algorithm 1.
Algorithm 1 The R-core of a graph
Input:
Graph G with loops allowed and without isolated vertices, vertex set denoted by V ,
neighborhoods NG(i), i ∈ V .
1: for i ∈ V do
2: W (i) = ∅
3: found = FALSE
4: for j ∈ V \ {i} do
5: if N(j) ⊆ N(i) then
6: W (i) :=W (i) ∪N(j)
7: end if
8: if N(i) ⊆ N(j) then
9: found = TRUE
10: end if
11: end for
12: if W (i) = N(i) ∧ found then
13: delete i from V
14: N(i) = ∅
15: end if
16: end for
17: return The R-core G[V ] of G.
The algorithm removes all vertices v ∈ G such that (1) the neighborhood of v is union
of neighborhood of some other vertices v1, v2, . . . , vn and (2) there is vertex u such that
340 Ars Math. Contemp. 6 (2013) 323–350
NG(v) ⊆ NG(u).
It is easy to see that the resulting graph H is relationally equivalent to G. Condition
(1) ensures the existence of a relation R1 such that H ∗ R1 = G, while the condition (2)
ensures the existence of a relation R2 such that G ∗R2 = H .
We need to show that H is isomorphic to GR-core. By Theorem 3.17 we can assume that
GR-core is an induced subgraph of H that is constructed as an induced subgraph of G.
We also know that there are relations R1 and R2 such that GR-core ∗ R1 = H and
G ∗ R2 = GR-core. By the same argument as in the proof of Theorem 3.17 we can assume
both R1 and R2 to contain an (restriction of) identity.
Now assume that there is a vertex v ∈ VH \VGR-core . We can put u = R2(v) and because
R2 contains an identity we have NG(v) ⊆ NG(u). We can also put {v1, v2 . . . vn} to be
set of all vertices such that v ∈ R1(vi). It follows that the neighborhood of v is the union
of neighborhoods of v1, v2, . . . , vn and consequently we have v /∈ VH , a contradiction.
4 The partial order Rel(G,H)
4.1 Basic properties
For fixed graphs G and H we consider partial order Rel(G,H). The vertices of this partial
order are all relations R such that G ∗R = H . We put R1 ≤ R2 if and only if R1 ⊆ R2.
This definition is motivated by Hom-complexes, see [10]. In this section we show the
basic properties of this partial order and concentrate on minimal elements in the special
case of Rel(G,G).
Proposition 4.1. Suppose G ∗ R′ = H , G ∗ R′′ = H and R′ ⊆ R′′, then any relation R
with R′ ⊆ R ⊆ R′′ also satisfies G ∗R = H .
Proof. FromR′ ⊆ R ⊆ R′′ we concludeG∗R′ ⊆ G∗R ⊆ G∗R′′. HenceG∗R′ = G∗R′′
implies G ∗R = H .
Hence it is possible to describe the partial order Rel(G,H) by listing minimal and
maximal solutions R of G ∗R = H w.r.t. set inclusion.
For example, if G is P3 with vertices v0, v1, v2, v3 and H is P1 with vertices x0, x1,
it is easily seen that R′′ = {(v0, x0), (v2, x0), (v1, x1), (v3, x1)} is a maximal solution of
G∗R = H andR′ = {(v0, x0), (v1, x1)} is a minimal solution, becauseR′ ⊂ R′′, then all
the relations R with R′ ⊆ R ⊆ R′′ satisfy G ∗R = H . We note that minimal and maximal
solutions need not be unique.
4.2 Solutions of G ∗ R = G
For simplicity, we say that a relation R is an automorphism of G if it is of the form R =
{(x, f(x))|x ∈ VG} and f : VG → VG is an automorphism of G.
We shall see that conditions related to thinness again play a major role in this context.
Recall that G is thin if no two vertices have the same neighborhood, i.e., NG(x) = NG(y)
implies x = y. Here we need an even stronger condition:
Definition 4.2. A graph G satisfies condition N if NG(x) ⊆ NG(y) implies x = y.
In particular, graph satisfying condition N is thin.
J. Hubička et al.: Relations between graphs 341
Proposition 4.3. For a given graphG, the set Rel(G,G) of all relations satisfyingG∗R =
G forms a monoid.
Proof. Firstly, because G is a finite graph, the set Rel(G,G) is also finite. Furthermore,
R,S ∈ Rel(G,G) implies G ∗ R = G and G ∗ S = G and thus G ∗ (R ◦ S) = G, so that
R◦S ∈ Rel(G,G). Finally, the identity relation IG is a left and right identity for relational
composition: IG ◦R = R ◦ IG = R.
A relation R ⊂ VG × VG can be interpreted as a directed graph ~R with vertex set
VG and a directed edge u → v if and only if (u, v) ∈ R. Note that ~R may have loops.
We say that v ∈ VG is recurrent if and only if there exists a walk (of length at least 1)
from v to itself. Let SG be the set of all the recurrent vertices. Furthermore, we define an
equivalence relation ξ on SG by setting (u, v) ∈ ξ if there is a walk in ~R from u to v and
vice versa. The equivalence classes w.r.t. ξ are denoted by ~R/ξ = {D1, D2, · · · , Dm}.
We furthermore define a binary relation ≥ over ~R/ξ as follows: if there is a walk from a
vertex u in Di to a vertex v in Dj , then we say u ≥ v. It is easily seen that ≥ is reflexive,
antisymmetric, and transitive, hence (~R/ξ,≥) is a partially ordered set. W.l.o.g. we can
assume {D1, D2, . . . , Ds} are the maximal elements w.r.t. ≥. Now let Gr = G[D1 ∪ · · · ∪
Ds] be the subgraph of G induced by these maximal elements.
In the following we write Rl for the l-fold composition of R with itself.
Lemma 4.4. For arbitrary x ∈ VG, there exists l ∈ N and a recurrent vertex v such that
(v, x) ∈ Rl.
Proof. Set x0 = x and choose xi ∈ R−1(xi−1) for all i ≥ 1. Since |VG| < ∞, there are
indices j, k ∈ N, j < k, xj = xk. Then xj is recurrent vertex. The lemma follows by
setting l = j and v = xi.
Lemma 4.5. For every v ∈ VGr , R−1(v) ⊆ VGr .
Proof. Suppose x ∈ R−1(v) is not recurrent. Lemma 4.4 implies that there is l ∈ N
and a recurrent vertex w such that (w, x) ∈ Rl. Hence the definitions of E and ≥ imply
[w] ≥ [v], where [v] denotes the equivalent class (w.r.t. E) containing the vertex v. Since
[v] is maximal w.r.t. ≥, we have [v] = [w]. Consequently, there exists an index k ∈ N such
that (v, w) ∈ Rk. On the other hand, we have (x, x) = (x, v) ◦ (v, w) ◦ (w, x) ∈ Rk+l+1.
Thus, x is recurrent, a contradiction.
Therefore, every vertex x ∈ R−1(v) is recurrent. Hence [x] ≥ [v] together with the
maximality of [v] gives [x] = [v], and thus x ∈ VGr .
Lemma 4.6. For every x ∈ VG, there is l ∈ N such that, for arbitrary i ≥ l, there exists
u ∈ VGr satisfying (u, x) ∈ Ri.
Proof. From Lemma 4.4 and Lemma 4.5 we conclude that it is sufficient to show that for
an arbitrary recurrent vertex v there is a k ∈ N and w ∈ VGr such that (w, v) ∈ Rk. The
lemma now follows easily from the finiteness of VG.
From these three lemmata we can deduce
Theorem 4.7. All solutions of G∗R = G are automorphisms if and only if G has property
N.
342 Ars Math. Contemp. 6 (2013) 323–350
Proof. Suppose there are distinct vertices x, y ∈ VG such that NG(x) ⊆ NG(y). Then
R = IG ∪ (x, y), which is not functional, satisfies G ∗ R = G. Thus G ∗ R = G is also
solved by relations that are not automorphisms of G. This proves the “only if” part.
Conversely, supposeG has property N. Claim: There is a k ∈ N such thatRk∩(VGr×
VGr ) = IGr .
For each vi ∈ VGr there is a walk of length si ≥ 1 from vi to itself. Hence (vi, vi) ∈
Rsi . Let s be the least common multiple of the si. Then (vi, vi) ∈ Rs for all vi ∈ VGr .
Define Q := Rs ∩ (VGr × VGr ). Thus IGr ⊆ Q and moreover Qj ⊆ Qj+1 for all j ∈ N.
Since VGr is finite there is an n ∈ N such that Qn+1 = Qn, and hence Q2n = Qn. Let
us write R−i(v) := {u ∈ VG : (u, v) ∈ Ri}. For v ∈ VGr we have R−i(v) ∈ VGr
(from Lemma 4.5) and hence Q−n(v) = R−sn(v) for all v ∈ VGr . If Qn 6= IGr , then
there are two distinct vertices u, v ∈ VGr , such that (u, v) ∈ Qn. NG(u) * NG(v) and
G = G ∗ Rsn allows us to conclude that R−sn(u) * R−sn(v) and R−sn(v) * R−sn(u).
Hence, there is a vertex w, such that (w, u) ∈ Qn and (w, v) /∈ Qn. From (u, v) ∈ Qn
and (w, u) ∈ Qn we conclude (w, v) ∈ Qn ◦ Qn = Q2n, contradicting to Q2n = Qn.
Therefore Qn = IGr . Setting k = sn now implies the claim.
Finally, we show VGr = VG. For any v ∈ VG\VGr , Lemma 4.6 implies the existence of
w ∈ VGr andm ∈ N such that (w, v) ∈ Rmk. However, we have claimedR−k(w) = {w},
hence R−mk(w) = {w}. This, however, implies NG(w) ⊆ NG(v) and thus contradicts
property N. Therefore, VG = VGr and moreover R
k = IG. This R is an automorphism.
5 R-retraction
A particularly important special case of ordinary graph homomorphisms are homomor-
phisms to subgraphs, and in particular so-called retractions: Let H be a subgraph of G, a
retraction of G to H is a homomorphism r : VG → VH such that r(x) = x for all x ∈ VH .
We introduced the graph cores in section 3 as minimal representatives of the homo-
morphism equivalence classes. The classical and equivalent definition is the following: A
(graph) core is a graph that does not retract to a proper subgraph. Every graph G has a
unique core H (up to isomorphism), hence one can speak of H as the core of G, see [7].
Here, we introduce a similar concept based on relations between graphs. Again to
obtain a structure related to graph homomorphisms, in this section we require all relations
to have full domain unless explicitly stated otherwise.
Definition 5.1. Let H be a subgraph of G. An R-retraction of G to H is a relation R such
that G ∗ R = H and (x, x) ∈ R for all x ∈ VH . If there is an R-retraction of G to H we
say that H is a retract of G.
Lemma 5.2. If H is an R-retract of G and K is an R-retract of H , then K is an R-retract
of G.
Proof. Suppose T is an R-retraction of H to K and S is an R-retraction of G to H . Then
(G ∗ S) ∗ T = G ∗ (S ◦ T ) = K. Furthermore (x, x) ∈ T for all x ∈ VK ⊆ VH , and
(u, u) ∈ S for all u ∈ VH , hence (x, x) ∈ S ◦ T for all x ∈ Vk. Therefore S ◦ T is an
R-retraction from G to K.
Hence, the following definition is meaningful.
J. Hubička et al.: Relations between graphs 343
Definition 5.3. A graph is R-reduced if there is no R-retraction to a proper subgraph.
Thus, we can also speak about “the R-reduced graph of a graph G” as the smallest
subgraph on which it can be retracted. We shall see below that the R-reduced graph of a
graph is always unique up to isomorphism.
We shall remark that R-reduced graphs differs from R-cores introduced in section 3,
thus we choose an alternative name used also in homomorphism setting (cores are also
called reduced graphs).
Lemma 5.4. Let G be a graph with loops and o a vertex of G with a loop on it. Then the
R-reduced graph of G is the subgraph induced by {o}.
Proof. Let O be the graph induced by {o}, and R = {(x, o)|x ∈ VG}, then it is easily
seen R is a R-retraction of G to O. Moreover, since O has only one vertex, thus there is no
R-retraction to its subgraphs. So O is a R-reduced graph of G.
Conversely, let H be a R-reduced graph of G and denote by R the R-retraction from
G to H . Then a loop of G must generate a loop of H via R, denote it by O. Similarly
to above, we see O is a R-retract of H , hence it is also a R-retract of G (by Lemma 5.2).
Therefore the definition of R-reduced graph implies H = O.
In the remainder of this section, therefore, we will only consider graphs without loops.
Lemma 5.5. If G is R-reduced, then G has property N.
Proof. Suppose there are two distinct vertices x, y ∈ VG with NG(x) ⊆ NG(y) and con-
sider the induced graph G/x := G[VG \ {x}] obtained from G by deleting the vertex x
and all edges incident with x. The relation R = {(z, z)|z ∈ VG \ {x}} ∪ {(x, y)} satisfies
G∗R = G/x: the first part is the identity onG/x and already generates all necessary edges
in G/x. The second part transforms edges of the form (x, z) ∈ EG to edges (y, z). Since
R has full domain and contains the identity relation restricted to G/x, it is an R-retraction
of graph G, and hence G is not R-reduced.
Proposition 5.6. A graph G is R-reduced if and only if it has no relation to a proper
subgraph.
Proof. The “if” part is trivial. Now we suppose that H is a proper induced subgraph of
graph G with the minimal number of vertices such that there is a relation R satisfying
G ∗R = H . Then H does not have a relation to a proper subgraph of itself. We claim that
H has property N; otherwise, one can find a vertex u ∈ VH and construct a retraction from
H to H/u as in Lemma 5.5, which causes a contradiction. Denote R̃ = R ∩ (VH × VH),
then K = H ∗ R̃ is a subgraph of H . From our assumptions on H we obtain K = H . By
virtue of Theorem 4.7, R̃ is induced by an automorphism of H . Hence R ◦ R̃+ is again a
relation of G to H that contains the identity on H , i.e., it is an R-retraction.
Since graph cores are induced subgraphs and retractions are surjective they also imply
relations. Proposition 5.6 is also a consequence of this fact. We refer to [7] for a formal
proof.
We callR a minimal R-retraction if there is no R-retractionR′ such thatR ⊃ R′ ⊃ IH .
Lemma 5.7. Let H be an R-retract of G. Then any minimal R-retraction of G to H is
functional.
344 Ars Math. Contemp. 6 (2013) 323–350
Figure 5: A graph G and its core.
Proof. Suppose R is a minimal R-retraction of G to H . If R is not functional, then there
exist distinct x, y ∈ VH such that (u, x), (u, y) ∈ R. Hence we could always pick a
vertex from {x, y} which is different of u, w.l.o.g. suppose it is x. Then R/(u, x) is an
R-retraction, which contradicts minimality. To see this, setR′ = R/(u, x), thenR ⊃ R′ ⊃
IH and moreover H = G ∗ IH ⊆ G ∗R′ ⊆ G ∗R = H , and thus G ∗R′ = H .
Proposition 5.8. A graph is R-reduced if and only if it is a graph core.
Proof. If H is R-reduced from G there is an R-retraction from G to H which can be
chosen minimal and hence by Lemma 5.7 is functional and hence is a homomorphism
retraction. Conversely, a homomorphism retraction is also an R-retraction. Hence the R-
reduced graphs coincide with the graph cores.
Proposition 5.9. Suppose H is the core of graph G. If H ∗R = K then there is a relation
R′ such that G ∗R′ = K. If K ∗ S = G, then there is a relation S′ such that K ∗ S′ = H .
Proof. Since H is the core of graph G, there is a relation R1 such that G ∗ R1 = H . If
H ∗R = K we haveG∗R1 ∗R = K andR′ = R1 ◦R satisfiesG∗R′ = K. IfK ∗S = G
we have K ∗ S ∗R1 = H and S′ = S ◦R1 satisfies K ◦ S′ = G.
5.1 Cocores
In the classical setting of maps between graphs, one can only consider retractions from a
graph to its subgraphs, since graph homomorphisms of an induced subgraph to the original
graph are just the identity maps. In the setting of relations between graphs, however, it
appears natural to consider relations with identity restriction between a graph and an in-
duced subgraph. This gives rise to notions of R-coretraction and R-cocore in analogy with
R-retractions and R-reduced graphs.
Definition 5.10. LetH be a subgraph of graphG. An R-coretraction ofH toG is a relation
R such that H ∗R = G and (x, x) ∈ R for all x ∈ VH . We say that H is an R-coretract of
G.
Lemma 5.11. If H is an R-coretract of graph G and K is an R-coretract of H , then K is
an R-coretract of G.
Proof. Suppose T is an R-coretraction of K to H and S is an R-coretraction of H to G.
Then (K ∗ T ) ∗ S = K ∗ (T ◦ S) = G. Furthermore (x, x) ∈ T for all x ∈ VK ⊆ VH ,
and (v, v) ∈ S for all v ∈ VH , hence (x, x) ∈ T ◦ S for all x ∈ VK . Therefore T ◦ S is an
R-coretraction from K to G.
J. Hubička et al.: Relations between graphs 345
Hence, the following definition is meaningful.
Definition 5.12. An R-coretract H of a graph G is an R-cocore of G if H does not have a
proper subgraph that is an R-coretract of H (and hence of G).
G cocore(G)
Figure 6: A graph and its cocore
Clearly, the reference to G is irrelevant: A graph G is an R-cocore if there is no
proper subgraph of G that is an R-coretract of G. Similarly, we call R to be a minimal
R-coretraction of H to G if there exists no R-coretraction R′, such that R′ ⊂ R.
Lemma 5.13. Let H be an R-coretract of graph G, and let R be a minimal R-coretraction
of H to G. Then the restriction of R to H equals IH .
Proof. Suppose R∩ (VH × VH) 6= IH and define R1 = R \ {(x, y) ∈ R : x, y ∈ VH , x 6=
y}. Then H ∗ R1 ⊆ H ∗ R = G. We claim that H ∗ R1 = H ∗ R and thus R1 is an
R-coretraction of H to R, contradicting the minimality of R.
To prove this claim, it is sufficient to show that any edge e ∈ EG is contained in
H ∗R1. If e is not incident with any vertex in VH or e ∈ EH , the conclusion is trivial. So
we only need to consider e = (z, u) with z ∈ EH and u ∈ VG \ VH . Since G = H ∗ R,
one can find x1, x2 ∈ VH such that (x1, z), (x2, u) ∈ R and (x1, x2) ∈ EH . Because
H ⊆ H ∗
(
IH ∪ (x1, z)
)
⊂ H ∗
(
R ∩ (VH × VH)
)
= H , we get NH(x1) ⊆ NH(z). It
follows that (z, x2) ∈ EH and hence e = (z, u) ∈ G ∗R1.
Like R-reduced graphs, R-cocores satisfy a stringent condition on their neighborhood
structure.
Definition 5.14. A graph G satisfies property N* if, for every vertex x ∈ VG, there is no
subset Ux ⊆ VG \ {x} such that
NG(x) =
⋃
y∈Ux
NG(y) (5.1)
In other words, no neighborhood can be represented as the union of neighborhoods of
other vertices of graph G.
Proposition 5.15. G is an R-cocore if and only if G has property N*.
Proof. Consider a vertex set Ux as in Definition 5.14 and suppose that there is a vertex
x ∈ VG such that NG(x) =
⋃
y∈Ux NG(y). Then the relation R := I \ (x, x) ∪ {(y, x) :
y ∈ Ux} is an R-coretraction from G/x to G. Thus G is not a R-cocore.
Conversely, suppose that G is not an R-cocore, let H be a coretract of G, and denote
by R a minimal R-coretraction of H to G. Then, by Lemma 5.13, R ∩ (VH × VH) = IH .
Consider a vertex v ∈ VG \ VH and set R−1(v) = {x1, · · · , xi}. Then N(v) =
⋃
iN(xi),
contradicting property N*.
346 Ars Math. Contemp. 6 (2013) 323–350
Proposition 5.16. The R-cocore of G is unique up to isomorphism.
Proof. We denote by N the collection of all open neighborhoods of vertices in G, i.e.,
N = {NG(x1), NG(x2), · · · , NG(xk)}, where VG = {x1, x2, · · · , xk}. From the defi-
nition of the R-cocore we know that the subcollectionM of N consisting of all the open
neighborhoods of vertices in R-cocore is a basis of N , i.e., any set in N can be expressed
by the union of some sets in M. W.l.o.g., we denote the vertex set in a R-cocore C of
G is {x1, x2, · · · , xm} where m ≤ k, then M = {NG(x1), NG(x2), · · · , NG(xm)}.
We claim that any element in {NG(x1), NG(x2), · · · , NG(xm)} cannot be expressed as
the union of other elements, i.e., M is a minimal basis. Otherwise, w.l.o.g., suppose
NG(x1) = ∪xkNG(xk), xk ∈ {x2, . . . , xm}. For any 1 ≤ k ≤ m, NG(xk) = NC(xk)
or NG(xk) = NC(xk) ∪ {xi|(xi, xk) ∈ EG,m + 1 ≤ i ≤ n}, so either NC(x1) =
∪xkNC(xk), xk ∈ {x2, . . . , xm} orNC(x1) = ∪xkNC(xk)∪{xi|(xi, xk) ∈ EG,m+1 ≤
i ≤ n, xk ∈ {x2, . . . , xm}}, the former contradicts to Proposition 5.15, which implies any
element in {NC(x1), NC(x2), · · · , NC(xm)} cannot be expressed as the union of other
elements, the latter is impossible because {xi|(xi, xk) ∈ EG,m + 1 ≤ i ≤ n, xk ∈
{x2, . . . , xm}} * C.
Now we prove that this minimal basis is unique. Note that in N we view any vertex
with the same neighborhood as the same, since any vertex in R-cocore has different neigh-
borhoods. Let us consider two minimal sub-collectionsA,B. Neither contains the other by
their minimality. Since everything is finite, let A ∈ A/B be an element of minimal size.
Now A can be expressed as a union of elements of B, which all need to be of smaller cardi-
nality than A (or same but A /∈ B), but A then contains all of them, letting A be expressed
by a union of elements of A contradicting the minimality of A.
These results allow us to construct an algorithm that computes the cocore of given graph
G in polynomial time. First observe that the cocore of a graph G that contains isolated
vertices is the disjoint union of cocore of the graph G′ obtained from G by removing
isolated vertices and the graph consisting of a single isolated vertex. It is thus sufficient to
compute cocores for graphs without isolated vertices in Algorithm 2.
Proposition 5.17. Suppose H is a cocore of G. If K ∗ R = H , then there is a relation R′
such that K ∗R′ = G. If G ∗ S = K, then there is a relation S′ such that H ∗ S′ = K.
Proof. Since H is a cocore of G, there exists an R-coretraction R1 such that H ∗R1 = G.
If K ∗ R = H , then letting R′ = R ◦ R1 implies K ∗ R′ = G. If G ∗ S = K, we have
H ∗R1 ∗ S = K. Let S′ = R1 ◦ S, then H ∗ S′ = K.
6 Computational complexity
In this section we briefly consider the complexity of computational problems related to
graph homomorphisms. The homomorphism problem HOM(H) takes as input some finite
G and asks whether there is a homomorphism fromG toH . The computational complexity
of the homomorphism problem is fully characterized. It is known that HOM(H) is NP-
complete if and only if H has no loops and contains odd cycles. All the other cases are
polynomial, see [7].
The analogous problem for relations between graphs can be phrased as follows: The
full relation problem FUL-REL(H) takes as input some finite G and asks whether there is
a relation with full domain from G and asks whether there is a relation from G to H . We
J. Hubička et al.: Relations between graphs 347
Algorithm 2 The cocore of a graph
Input:
Graph G with loops and without isolated vertices specified by its vertex set V and the
neighborhoods NG(i), i ∈ V .
1: for i ∈ V do
2: W (i) = ∅
3: for j ∈ V \ {i} do
4: if N(j) ⊆ N(i) then
5: W (i) :=W (i) ∪N(j)
6: end if
7: end for
8: if W (i) = N(i) then
9: delete i from V
10: N(i) = ∅
11: end if
12: end for
13: return G[V ], the cocore of G.
show that this problem can be easily converted to a related problem on surjective homo-
morphisms. The surjective homomorphism problem SUR-HOM(H) takes as input some
finite G and asks whether there is a surjective homomorphism from G to H .
Let ≤TurP indicate polynomial time Turing reduction.
Theorem 6.1. For finite H our relation problem sits in the following relationship.
HOM(H) ≤TurP FUL-REL(H) ≤TurP SUR-HOM(H) . (6.1)
Proof. First we show that HOM(H) is polynomially reducible to FUL-REL(H). If there is
a homomorphism from G to H , then there is also a surjective homomorphism from G+H
to H . On the other hand, suppose G has no homomorphism to H . From Lemma 1.4 we
conclude that G+H has no relation to H since G has no relation to H .
The relation problem FUL-REL(H) is polynomially reducible to SUR-HOM(H). From
Corollary 2.3 we know G ∗R = H if and only if there is a graph G′ = G ∗RD which has
a full homomorphism to G and has a surjective homomorphism to H .
We construct G′′, by duplicating all the vertices of G precisely |VH | times. It is easy to
see that if G′ exists, we can also put G′ = G′′ because the surjective homomorphism can
easily undo the redundant duplications.
It remains to check whether there is surjective homomorphism from G′′ to H . This
gives the polynomial reduction from FUL-REL(H) to SUR-HOM(H).
To our knowledge, SUR-HOM(H) is not fully classified. A recent survey of the closely
related complexity problem concerning the existence of vertex surjective homomorphisms
[2] provides some arguments why the characterization of complexity is likely to be hard,
see also [5]. We observe that the existence of a homomorphism from G to H is equivalent
to the existence of a surjective homomorphism from G + H to H . Thus SUR-HOM(H)
is clearly hard for all graphs for which HOM(H) is hard, i.e., for all loop-less graphs with
odd cycles.
348 Ars Math. Contemp. 6 (2013) 323–350
Testing the existence of a homomorphism from a fixed G to H is polynomial (there is
only a polynomial number |VH ||VG| of possible functions from G to H). Similarly the ex-
istence of a relation from a fixed G to H is also polynomial. In fact, an effective algorithm
exists. For fixed G there are finitely many thin graphs T which G has relation to. The al-
gorithm thus first constructs the thin graph of H and then, using a decision tree recognizes
all isomorphic copies of all thin graphs G has relation to.
7 Weak relational composition
In this section we will briefly discuss the “loop-free” version, i.e., equations of the form
G ? R = H .
Most importantly, there is no simple composition law analogous to Lemma 2.1. The
expression
(G ? R) ? S = (S+ ◦ (R+ ◦G ◦R)ι ◦ S)ι (7.1)
does not reduce to relational composition in general. For example, let G = K3 with vertex
set V = {x, y, z} and consider the relations R = {(x, 1), (z, 1), (y, 2)} ⊆ {x, y, z} ×
{1, 2} and S = {(1, x′)(1, z′)(2, y′)} ⊆ {1, 2} × {x′, y′, z′}. One can easily verify
(G ? R) ? S = P2 6= G ? (R ◦ S) = K3 (7.2)
The most important consequence of the lack of a composition law is that R-retractions
cannot be meaningfully defined for the weak composition. Similarly, the results related to
R-equivalence heavily rely on the composition law.
Nevertheless, many of the results, in particular basis properties derived in section 2, re-
main valid for the weak composition operation. As the proofs are in many cases analogous,
we focus here mostly on those results where strong and weak composition differ, or where
we need different proofs. In particular, Lemma 2.2 also holds for the weak composition.
Thus, we still have a result similar to corollary 2.3, but the proof is slightly different.
Corollary 7.1. Suppose G ? R = H . Then there is a set C, an injective relation RD ⊆
domR×C, and a surjective relation RC ⊆ C× imgR such that G[domR] ?RD ?RC =
H[imgR].
Proof. From Proposition 2.2 we know R = I ′ ◦RD ◦RC ◦ I ′′. And we know G[domR] ?
RD = G[domR] ∗RD. From the properties of ?, we have
G[domR] ? R = (R+ ◦G[domR] ◦R)l
= ((RD ◦RC)+ ◦G[domR] ◦RD ◦RC)l
= (R+C ◦R+D ◦G[domR] ◦RD ◦RC)l
= (R+C ◦ (R+D ◦G[domR] ◦RD) ◦RC)l
= (R+C ◦G[domR] ∗RD ◦RC)l
= (R+C ◦G[domR] ? RD ◦RC)l
= G[domR] ? RD ? RC
= H[imgR]
.
J. Hubička et al.: Relations between graphs 349
Assume G ? R = H and let H1, · · · , Hk the connected components of H . From the
definition of ? and ∗, if we denote H̃ = G∗R, then H̃ could be decomposed into the union
of connected components H̃i(1 ≤ i ≤ k), such that (H̃i)ι = Hi. Hence the conclusion of
the proposition 2.4 also holds true for weak relations.
Lemma 2.6 does not hold for weak relations. For example, there is a weak relation of
K5 to K3, but χ(K5) = 5 > χ(K3) = 3.
Lemma 2.7 and Lemma 2.8 do not hold for weak relations. For example, ifG is a graph
consisting of a single isolated vertex, then P3 ? R = G and C3 ? R = G, but there are no
walk in G.
With respect to complete graphs, weak relational composition also behaves different
from strong composition. If Kk ? R = H then R(i) can contain more that one vertex in
VH . Compared to Proposition 2.12, we also obtain a different result:
Theorem 7.2. There is a relation R such that Kk ? R = H if and only if every connected
component of H is a complete graph, and the number of connected components of H
containing at least 2 vertices is at most k.
Proof. If every connected component of H is a complete graph, denoted the vertex sets of
the connected components containing at least 2 vertices by H1, . . . ,Hm, m ≤ k and the
vertices of Kk by 1, · · · , k. Let R = {(i, u)|i = 1, · · · , k, u ∈ VHi} ∪ {(j, v) : 1 ≤ j ≤
k, v ∈ VH \
⋃m
i=1 VHi}. One easily checks that Kk ? R = H .
Conversely, let R be a relation satisfying Kk ? R = H . Consider the set Ui = {u ∈
VH |R−1(u) = {i}}. Then u and v are not adjacent for arbitrary u, v ∈ Ui, while u is
adjacent to w for every w ∈ VH \Ui. Hence H(Ui) is a connected component of H , which
is also a complete graph. Given w ∈ VH \
⋃m
i=1 Ui,R
−1(w) must have at least 2 vertices in
Kk, hence w is adjacent to every vertex in H except itself; in other words, w is an isolated
vertex in H . Therefore the number of connected components of H containing at least 2
vertices is no more than k.
The results in subsection 3.1 also remain true for weak relations.
Acknowledgments
We thank Rostislav Matveev for helpful discussions in the beginning of the project and
pointing out the decomposition as in Lemma 2.3, and to Jaroslav Nešetřil for pointing out
the equivalence of some complexity problems and enlightening questions for further works.
L.Y. is grateful to the Max Planck Institute for Mathematics in the Sciences in Leipzig for
its hospitality and continuous support. This work was supported in part by the NSFC (to
L.Y.), the VW Foundation (to J.J. and P.F.S.), the Czech Ministry of Education, and ERC-
CZ LL-1201, and CE-ITI of GAČR (to J.H).
References
[1] E. Babson and D. Kozlov, Complexes of graph homomorphisms, Israel J. Math. 152 (2006),
285–312.
[2] M. Bodirsky, J. Kára and B. Martin: The complexity of surjective homomorphism problems —
a survey, Discr. Appl. Math. 160 (2012), 1680–1690.
[3] S. N. Dorogovtsev and J. F. F. Mendes, Evolution of Networks: From Biological Nets to the
Internet and WWW, Oxford Univ. Press, Oxford, UK, 2003.
350 Ars Math. Contemp. 6 (2013) 323–350
[4] T. Feder and P. Hell, On realizations of point determining graphs, and obstructions to full
homomorphisms, Discrete Math. 308 (2008), 1639–1652.
[5] P. A. Golovach, B. Lidický, B. Martin and D. Paulusma: Finding vertex-surjective graph ho-
momorphisms, Acta Informatics 49 (2012), 381–394.
[6] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Discrete Mathematics
and Its Applications, CRC Press, Boca Raton, FL, 2011.
[7] P. Hell and J. Nešetřil, Graphs and homomorphisms, Oxford University Press, Oxford, UK,
2004.
[8] J. Hubička, J. Fiala and Y. Long: Constrained homomorphism orders, in preparation, 2012.
[9] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition, Wiley, New York,
2000.
[10] J. Matoušek, Using the Borsuk-Ulam Theorem, Springer, Berlin, DE, 2003.
[11] M. E. J. Newman, Networks: An Introduction, Oxford Univ. Press, Oxford, UK, 2010.
[12] A. Schrijver, Combinatorial optimization: B, Springer, Berlin, 2003.
[13] D. P. Sumner, Point determination in graphs, Discrete Mathematics 5 (1973), 179–187.
[14] S. Wuchty and E. Almaas, Evolutionary cores of domain co-occurrence networks, BMC Evol.
Biol. 5 (2005), 24.
[15] Y. Xiao, B. D. MacArthur, H. Wang, M. Xiong and W. Wang, Network quotients: Structural
skeletons of complex systems, Phys. Rev. E 78 (2008), 046 102.
[16] A. Zhang: Protein interaction networks: computational analysis. Cambridge University Press,
Cambridge, UK, 2009.