We introduce and investigate a new class of graph maps, called backward edge-preserving maps. These are the maps between the vertex sets of graphs such that the pre-image of every edge in the target graph is an edge in the source graph. We give a complete structural characterization of such maps for both general and connected graphs. We also explore the relationship between backward edge-preserving maps, metric maps, and graph homomorphisms, and establish criteria for the intersection of these classes. Furthermore, we study a related class of graph cohomomorphisms and establish conditions under which a map can simultaneously be a homomorphism and a cohomomorphism.
Maps between graphs play a central role in modern graph theory and its applications. Perhaps the most studied among them are graph homomorphisms, which preserve adjacency and serve as a natural abstraction of structure-preserving transformations (see the book [5]).
Beyond homomorphisms, several other classes of graph maps have been studied, each emphasizing different structural aspects. Among them, cut-continuous maps [2] which are maps \(f: E(G) \to E(H)\) between edge sets of two graphs \(G\), \(H\) such that the pre-image of any cut in \(H\) is a cut in \(G\) (here, a cut is the edge set of a spanning bipartite induced subgraph). It is clear that a graph homomorphism induces a cut-continuous map. A similar class of maps is given by cycle-continuous maps [2] which are maps defined on edge sets satisfying the following similar property: the pre-image of any cycle is a cycle. A more sophisticated class of graph maps is given by tension-continuous maps (or shortly, TT maps). They also have emerged as a natural extension of homomorphisms, preserving algebraic properties of the so-called graph tensions. A TT map from \(G\) to \(H\) is a map \(f: E(G) \to E(H)\) such that for every tension on \(H\), the pullback along \(f\) yields a tension on \(G\) (see [8, 9]). These maps are dual to flow-continuous maps and play an important role in the context of nowhere-zero flows and cut/cycle dualities. TT maps induce a quasiorder on graphs, generalizing the classical homomorphism order, and have been used to study structural properties of graphs, including universality and Ramsey-type phenomena.
Another line of research concerns graph vertex maps that preserve more global structural properties, such as graph distance. An interesting example arises in the context of Grassmann graphs, where distance-preserving maps are those which preserve the graph-theoretic distance between vertices. These maps are often induced by semilinear embeddings between associated vector spaces and have been thoroughly studied in relation to projective and algebraic geometry [6].
In this paper, we study a new class of graph maps, which we call backward edge-preserving maps (or BEP maps, for short). A map \(f : V(G) \to V(H)\) is said to be BEP if the pre-image \(f^{-1}(e)\) of every edge \(e \in E(H)\) is an edge in \(G\). This class of maps is a strict subclass of a known class of graph cohomomorphisms [4]. While the definition of BEP maps may appear dual to that of a homomorphism, BEP maps behave quite differently and give rise to novel combinatorial properties.
This paper is organized as follows. In Section 2, we give all the preliminary definitions that will be used throughout the paper.
Section 3.1 contains our main results on BEP maps. Theorem 3.1 gives a full structural characterization of BEP maps between arbitrary graphs. This result is clarified for connected graphs \(H\) in Corollary 3.2. The intersection of classes of metric maps and BEP maps are described in Theorem 3.5. In particular, the criterion of BEP maps in the class of graph homomorphisms is given in Proposition 3.6. Theorem 3.10 shows that the classes of cohomomorphisms and metric maps between complements differ even in the class of graph homomorphisms.
In Section 3.2, we investigate the properties of graph cohomomorphisms. In Proposition 3.7, we give a characterization of this class of maps, and then obtain a criterion of the intersection of classes of homomorphisms and cohomomorphisms (Corollaries 3.8 and 3.9).
We note that several results from Section 3.2 of this paper were announced in 2024 at the XII All-Ukrainian conference of young mathematicians [3].
In this paper, all graphs are undirected, simple and finite. Two vertices \(u,v\in V(G)\) in a graph \(G\) are called adjacent if \(\{u,v\}\in E(G)\). By \(N_{G}(u)=\{v\in V(G):\{u,v\}\in E(G)\}\) we denote the neighborhood of \(u\) in \(G\). The degree of a vertex \(u\) is the number of vertices adjacent to it, i.e., the cardinality of \(N_{G}(u)\). A vertex with zero degree is called isolated. By \(\mathop{\mathrm{Iso}}(G)\) we will denote the set of isolated vertices in \(G\).
By \(\overline{G}\) we denote the complement of a graph \(G\), where \(V(\overline{G})=V(G)\) and \(\{u,v\}\in E(\overline{G})\) if and only if \(\{u,v\}\notin E(G)\).
A graph \(H\) is a subgraph of a graph \(G\) if \(V(H)\subset V(G)\) and \(E(H)\subset E(G)\). If \(V(H)=V(G)\) then \(H\) is called a spanning subgraph. For a set of vertices \(A\subset V(G)\), by \(E_{G}(A)\) we denote the set of all edges with endpoints in \(A\). A subgraph \(H\) of \(G\) is induced provided \(E(H)=E_{G}(V(H))\). By \(G[A]\) we denote the subgraph of \(G\) induced by the set of vertices \(A\subset V(G)\). For a set of vertices \(A\subset V(G)\), by \(G-A\) we denote the induced subgraph \(G[V(G)\setminus A]\).
A set of vertices is independent if no two of its vertices are adjacent. A set \(A\subset V(G)\) is a vertex cover if for every edge \(e\in E(G)\) we have \(e\cap A\neq\emptyset\). A set of edges \(E'\subset E(G)\) is a matching provided no two of edges from \(E'\) share a common vertex. A matching \(E'\) is perfect if each vertex \(u\in V(G)\) is incident to some edge \(e\in E'\).
Given an equivalence relation \(R\) on the set of vertices \(V(G)\) of a graph \(G\), by \({G}/{R}\) we denote the corresponding factor-graph, where \(V({G}/{R})=V(G)/{R}\), and the two equivalence classes \([u]_{R}\) and \([v]_{R}\) are adjacent provided \(\{x,y\}\in E(G)\) for some \(x\in[u]_{R}\), \(y\in[v]_{R}\).
A graph is connected if every pair of its vertices are joined by a path. A subset of vertices \(A\subset V(G)\) is called connected provided the induced subgraph \(G[A]\) is connected. A connected component of \(G\) is a maximal connected subgraph in \(G\). An edge is called isolated provided it is a connected component in a graph.
A vertex in a graph is called a cut vertex if its deletion increases the number of connected components. A graph with no cut vertices is called biconnected. A block in a graph is its maximal biconnected subgraph.
A proper coloring of a graph \(G\) is a map \(f:V(G)\to X\) such that for every edge \(\{u,v\}\in E(G)\), we have \(f(u)\neq f(v)\).
The vertex set of a connected graph \(G\) is equipped with the standard graph distance \(d_{G}(x, y)\), defined as the length (i.e., the number of edges) of a shortest path between the vertices \(x\) and \(y\).
A map \(f:V(G)\to V(H)\) between vertex sets of two graphs \(G\) and \(H\) is called a homomorphism if the image of every edge \(\{u,v\}\in E(G)\) is an edge \(\{f(u),f(v)\}\in E(H)\). Naturally, this class of maps received the most attention in the literature (see [5], for example). An isomorphism is a bijective homomorphism \(f\) such that its inverse map \(f^{-1}\) is also a homomorphism.
One generalization of graph homomorphisms is given by the so-called metric maps. A map \(f:V(G)\to V(H)\) between two connected graphs is called metric (or \(1\)-Lipschitz, or non-expanding, or contraction) provided \[d_{H}(f(u),f(v))\leq d_{G}(u,v),\] for all \(u,v\in V(G)\).
The following result shows that metric maps indeed generalize graph homomorphisms.
Proposition 2.1. [7, Proposition] A map \(f: V(G) \to V(H)\) is metric if and only if for every edge \(\{u,v\} \in E(G)\), we have \(d_{H}(f(u), f(v)) \leq 1\).
Metric maps, along with several other classes of maps between graphs, were studied in [11] under the name of non-expanding maps. In particular, it was shown that any metric map from a graph \(G\) to itself has either a fixed point or an invariant thick cycle (see [11, Theorem 1]).
In the case of trees \(T\), any metric self-map \(f\) of \(T\) must have either a fixed point or an inverted edge, that is, an edge \(\{u,v\} \in E(T)\) such that \(f(u) = v\) and \(f(v) = u\).
More generally, an infinite graph \(G\) has the property that every metric self-map has an invariant edge (an edge \(\{u,v\} \in E(G)\) such that \(\{f(u), f(v)\} = \{u,v\}\)) if and only if \(G\) is a tree with no infinite paths [10].
Another useful characterization of metric maps is provided by the next result.
Proposition 2.2. [1] A map \(f:V(G)\to V(H)\) is metric if and only if the image \(f(A)\) of every connected set \(A\subset V(G)\) is connected in \(H\).
A map \(f : V(G) \to V(H)\) is said to be monotone if the pre-image \(f^{-1}(y)\) of every vertex \(y \in V(H)\) is a connected subset in \(G\).
For instance, every injective map is monotone. Furthermore, the classes of homomorphisms, isomorphisms, and metric maps are closed under composition. This, however, does not hold for monotone maps. In fact, monotone self-maps \(f : V(G) \to V(G)\) generate the full transformation semigroup on \(V(G)\) (see [7, Proposition 2.9]). Moreover, when \(G\) is a path, every self-map of \(V(G)\) can be expressed as a composition of exactly two monotone maps [7, Proposition 2.10].
A map \(f:V(G)\to V(H)\) between two graphs \(G,H\) is called backward edge-preserving, or just a BEP map if \(f^{-1}(e)\in E(G)\) for all \(e\in E(H)\).
For example, consider a \(4\)-vertex path \(G=\{1-2-3-4\}\), a \(3\)-vertex path \(H=\{a-b-c\}\), and a map \(f:V(G)\to V(H)\) with \(f(1)=f(2)=a\), \(f(3)=f(4)=c\). One can easily verify that \(f\) is a BEP map. Further, any map into the empty graph \(H=\overline{K}_{n}\) is a BEP map, and any bijective map from the complete graph \(G=K_{n}\) is a BEP map as well. The last example easily generalizes to bijective maps \(f\) with \(f^{-1}\) being homomorphisms. In other words, if a graph \(H\) is a spanning subgraph of \(G\), then the identity map between \(V(G)\) and \(V(H)\) is BEP.
To characterize BEP maps between arbitrary graphs (possibly disconnected), we need two additional notations. For a map \(f\colon X\to Y\), define \[\mathop{\mathrm{Im}}_{1}{f}=\{y\in Y:|f^{-1}(y)|=1\}\ \text{and} \ \mathop{\mathrm{Im}}_{2}{f}=\{y\in Y:|f^{-1}(y)|=2\}.\]
Theorem 1. A map \(f\colon V(G)\to V(H)\) between two graphs \(G\) and \(H\) is BEP if and only if the next three conditions hold:
(a) every \(y\in\mathop{\mathrm{Im}}{f}\) with \(|f^{-1}(y)|\geq 3\) is an isolated vertex in \(H\);
(b) for every connected component \(H'\) of \(H\) with \(V(H')\cap \mathop{\mathrm{Im}}_{1}{f}\neq\emptyset\), we have: \(V(H')\subset \mathop{\mathrm{Im}}_{1}{f}\), and the restriction of \(f^{-1}\) to \(V(H')\) is a homomorphism from \(H'\) to \(G\);
(c) for every connected component \(H'\) of \(H\) with \(V(H')\cap \mathop{\mathrm{Im}}_{1}{f}=\emptyset\) and \(|V(H')|\geq 2\), we have: the set \(V(H')\cap \mathop{\mathrm{Im}}_{2}{f}\) is an independent vertex cover in \(H'\), and \(f^{-1}(y)\in E(G)\) for all \(y\in V(H')\cap \mathop{\mathrm{Im}}_{2}{f}\).
Proof. Necessity. Suppose that \(f\colon V(G)\to V(H)\) is a BEP map. Let us show that each of the three listed conditions must hold.
(a) Fix \(y\in \mathop{\mathrm{Im}}{f}\) with \(|f^{-1}(y)|\geq 3\) (see Figure 1, case \(1\)). Assume there exists a vertex \(y'\in V(H)\) with \(\{y,y'\}\in E(H)\). Then, it must hold that \(|f^{-1}(\{y,y'\})|=2\), because \(f\) is BEP. However, \[|f^{-1}(\{y,y'\})|=|f^{-1}(y)\cup f^{-1}(y')|\geq |f^{-1}(y)|\geq 3,\] which violates the definition of a BEP map.
(b) Now suppose \(H'\) is a connected component of \(H\) that intersects \(\mathop{\mathrm{Im}}_{1}{f}\). Put \(A=V(H')\cap\mathop{\mathrm{Im}}_{1}{f}\), and \(B=V(H')\backslash\mathop{\mathrm{Im}}_{1}{f}\). Clearly, \(A\sqcup B=V(H')\) and \(|A|>0\). If \(|B|>0\), then there exists an edge \(\{u,v\}\in E(H')\) with \(u\in A\), \(v\in B\), as \(H'\) is connected. Since \(f\) is BEP, \(|f^{-1}(\{u,v\})|=2\). Thus, \(|f^{-1}(v)|=|f^{-1}(\{u,v\})|-|f^{-1}(u)|=1\). But this implies \(v\in A\), which contradicts the fact that \(v\in B\). Hence, we conclude that \(|B|=0\), implying \(V(H')\subset \mathop{\mathrm{Im}}_{1}{f}\).
Since \(V(H')\subset \mathop{\mathrm{Im}}_{1}{f}\), there exists an inverse map \(f^{-1}:V(H')\to V(G)\). And because \(f\) is BEP, this map must be a homomorphism (see Figure 1, case \(2\)).
(c) Take any connected component \(H'\) of \(H\) satisfying both \(V(H')\cap \mathop{\mathrm{Im}}_{1}{f}=\emptyset\) and \(|V(H')|\geq 2\). Fix an arbitrary edge \(\{y,y'\}\in E(H')\). Since \(f\) is BEP, the pre-image of this edge must be an edge in \(G\). Note that \(f^{-1}(\{y,y'\})=f^{-1}(y)\sqcup f^{-1}(y')\). Since neither of these sets is a singleton, one of them must be empty, and the other must have cardinality equal to a power of \(2\). This proves that \(V(H')\cap \mathop{\mathrm{Im}}_{2}{f}\) is an independent vertex cover in \(H'\). Now fix a vertex \(y\in V(H')\cap \mathop{\mathrm{Im}}_{2}{f}\) (see Figure 1, case \(3\)). Given any neighbor \(y'\), the pre-image of the edge \(\{y,y'\}\) must be an edge in \(G\). But \(f^{-1}(y')=\emptyset\), since \(V(H')\cap \mathop{\mathrm{Im}}_{2}{f}\) is an independent vertex cover. Thus, \(f^{-1}(y)\in E(G)\).
Sufficiency. Now, suppose that \(f\colon V(G)\to V(H)\) is an arbitrary map satisfying the three conditions listed in the theorem’s statement. We need to prove that \(f\) is BEP. Let \(e\) be an edge in \(H\) that belongs to a connected component \(H'\). Now, there are two cases:
(a) \(V(H')\cap \mathop{\mathrm{Im}}_{1}{f}\neq\emptyset\). In this case, it follows from the second condition that both vertices incident to \(e\) belong to \(\mathop{\mathrm{Im}}_{1}{f}\). Also, the pre-image restricted to \(H'\) is a homomorphism, which in turn implies that \(e\) must be mapped to an edge in \(G\).
(b) \(V(H')\cap \mathop{\mathrm{Im}}_{1}{f}=\emptyset\). Again, we can immediately infer that \(f^{-1}(e)\in E(G)\), since exactly one of the vertices in \(e\) has a pre-image of cardinality \(2\) (the other’s pre-image is empty), and this pre-image must be an edge.
Thus, in both cases \(f^{-1}(e)\in E(G)\), which implies that \(f\) is BEP. ◻
The result in Theorem 3.1 can be clarified for connected
graphs \(H\). Note that any map into a
\(1\)-vertex graph \(H=K_{1}\) is a BEP map.
Corollary 3.2. Let \(G\) be a graph, and \(H\) be a connected graph with at least two vertices. Then a map \(f\colon V(G)\to V(H)\) is BEP if and only if it satisfies one of the following two conditions:
(a) the image \(\mathop{\mathrm{Im}}{f}\) is an independent vertex cover in \(H\), and \(f^{-1}(y)\in E(G)\) for all \(y\in\mathop{\mathrm{Im}}{f}\);
(b) the map \(f\) is bijective with \(f^{-1}\) being a homomorphism from \(H\) to \(G\).
Proof. Sufficiency. In this part of the proof, we verify that a map \(f\colon V(G)\to V(H)\) is BEP, given that it satisfies one of the two conditions listed above. Let us consider these two cases separately:
(a) Assume that \(f\) satisfies the first condition. It follows from the fact that \(\mathop{\mathrm{Im}}{f}\) is an independent vertex cover in \(H\) that for every edge \(\{y,y'\}\in E(H)\) exactly one of the vertices \(y\) or \(y'\) belongs to \(\mathop{\mathrm{Im}}{f}\). Without loss of generality, suppose that it is \(y\). Then \(f^{-1}(\{y,y'\})=f^{-1}(y)\). But \(f^{-1}(y)\in E(G)\), and this is true for every vertex in \(\mathop{\mathrm{Im}}{f}\). Thus, \(f\) is BEP.
(b) Now suppose that \(f\) is bijective and \(f^{-1}\) is a homomorphism from \(H\) to \(G\). Then it is apparent that for every edge \(e\in E(H)\), we have \(f^{-1}(e)\in E(G)\), which implies that \(f\) is BEP.
Necessity. Consider a BEP map \(f\colon V(G)\to V(H)\). We aim to prove that it must satisfy one of the two listed conditions. The second condition of Theorem 3.1 asserts that if there exists a vertex \(y\in V(H)\cap\mathop{\mathrm{Im}}_{1}{f}\), then \(V(H)\subset\mathop{\mathrm{Im}}_{1}{f}\). Also, in this case, the inverse map \(f^{-1}\) must be a homomorphism. This means that \(f\) is bijective with \(f^{-1}\) being a homomorphism from \(H\) to \(G\). Now, if such a vertex \(y\) cannot be found, then the third condition (which can be applied since \(|V(H)|\geq 2\)) claims that \(V(H)\cap \mathop{\mathrm{Im}}_{2}{f}\) is an independent vertex cover in \(H\), and that \(f^{-1}(y)\in E(G)\) for all \(y\in V(H')\cap \mathop{\mathrm{Im}}_{2}{f}\). But this exactly corresponds to the first condition of the corollary. To draw this conclusion it only remains to notice that \(\mathop{\mathrm{Im}}_{2}{f}=\mathop{\mathrm{Im}}{f}\), which follows from the first condition: if the cardinality of the pre-image of a vertex is at least \(3\), then it must be an isolated vertex, and \(H\) obviously has none. This observation concludes the proof. ◻
Remark 3.3. Let \(f:V(G)\to V(H)\) be a BEP map that satisfies the first condition from Corollary 3.2. Then the edge set \(\{f^{-1}(y):y\in\mathop{\mathrm{Im}}{f}\}\) is a perfect matching in \(G\). Also, the image \(\mathop{\mathrm{Im}}{f}\) being an independent vertex cover in \(H\) asserts that \(H\) must be bipartite.
Remark 3.4. Any BEP map into a graph without isolated vertices is monotone. To see this, suppose \(f\) is a BEP map between two graphs \(G\) and \(H\), and \(H\) has no isolated vertices. Pick an arbitrary vertex \(x\in V(H)\). Since \(x\) is not isolated in \(H\), there exists \(y\in V(H)\) with \(\{x,y\}\in E(H)\). Since \(f\) is BEP, it holds \(e=f^{-1}(\{x,y\})\in E(G)\). But \(f^{-1}(x)\subset e\). Hence, \(f^{-1}(x)\) must be connected. It immediately follows that \(f\) is monotone.
Now, we use Proposition 2.1 in order to define metric maps between general graphs (possibly disconnected): a map \(f:V(G)\to V(H)\) will be called metric provided \(f(u)=f(v)\) or \(\{f(u),f(v)\}\in E(H)\) for all edges \(\{u,v\}\in E(G)\). With this generalization in mind, we present characterization of BEP maps in the class of metric maps.
Theorem 3.5. A map \(f:V(G)\to V(H)\) between two graphs \(G,H\) is metric and BEP at the same time if and only if for any connected component \(H'\) in \(H\), at least one of the following conditions holds:
(a) the induced subgraph \(G':=G[f^{-1}(V(H'))]\) is a connected component in \(G\), and the restriction of \(f\) to \(V(G')\) induces an isomorphism between \(G'\) and \(H'\);
(b) \(|V(H')|\geq 2\), the subset \(V(H')\cap\mathop{\mathrm{Im}}_{2}{f}\) is an independent vertex cover in \(H'\), and for every \(y\in V(H')\cap\mathop{\mathrm{Im}}_{2}{f}\), the pre-image \(f^{-1}(y)\) induces an isolated edge in \(G\);
(c) \(|V(H')|=1\), and the pre-image \(f^{-1}(V(H'))\) induces a (possibly, empty) union of several connected components in \(G\).
Proof. Necessity. Suppose \(f:V(G)\to V(H)\) is a BEP metric map, and \(H'\) is a connected component in \(H\).
First, let \(|V(H')|=1\). Since \(H'\) is a connected component in \(H\), it follows from Proposition 2.2 that \(f^{-1}(V(H'))\) is a (possibly, empty) union of connected components. Thus, \(H'\) satisfies the third condition. In case \(H'\) has more than one vertex, consider two different possibilities:
(a) \(V(H')\cap \mathop{\mathrm{Im}}_{1}{f}\neq\emptyset\).
Theorem 3.1 asserts that \(V(H')\subset\mathop{\mathrm{Im}}_{1}{f}\), and \(f^{-1}:V(H')\to V(G)\) is a homomorphism. This implies that \(f^{-1}(V(H'))\) is connected, as homomorphisms map connected sets into other connected sets. Then, by Proposition 2.2, \(G':=G[f^{-1}(V(H'))]\) is a connected component in \(H\). Also, note that the restriction of \(f\) to \(V(G')\) is a homomorphism into \(V(H')\), as it is an injective metric map. Thus, both \(f\) and \(f^{-1}\) are homomorphisms as maps between \(G'\) and \(H'\), which implies that \(f\) induces an isomorphism between these two subgraphs. Thus, \(f\) satisfies the first condition.
(b) \(V(H')\cap \mathop{\mathrm{Im}}_{1}{f}=\emptyset\).
Applying the third condition of Theorem 3.1, we obtain that \(V(H')\cap \mathop{\mathrm{Im}}_{2}{f}\) is an independent vertex cover in \(H'\), and \(f^{-1}(y)\in E(G)\) for all \(y\in V(H')\cap \mathop{\mathrm{Im}}_{2}{f}\). This almost exactly corresponds to the second case from the theorem’s statement. The only thing that remains to be shown is that the edge \(f^{-1}(y)\) is isolated (for each \(y\in V(H')\cap\mathop{\mathrm{Im}}_{2}{f}\)). To see this, first observe that \(y\) is an isolated vertex in \(\mathop{\mathrm{Im}}{f}\). Indeed, for a neighboring vertex \(y'\) it is true that: \(y'\notin \mathop{\mathrm{Im}}_{1}{f}\) since \(V(H')\cap \mathop{\mathrm{Im}}_{1}{f}=\emptyset\), \(y'\notin \mathop{\mathrm{Im}}_{2}{f}\) since \(V(H')\cap \mathop{\mathrm{Im}}_{2}{f}\) is an independent vertex cover, and Theorem 3.1 asserts that \(|f^{-1}(y')|\geq 3\) cannot hold either, as in this case we would have \(|V(H')|=1\). But then it follows from Proposition 2.2 that the whole connected component in \(G\) that contains \(f^{-1}(y)\) must be mapped to \(y\) itself.
Sufficiency. Suppose \(f:V(G)\to V(H)\) is such a map that each of the connected components in \(H\) satisfies one of the three conditions above. Let us prove that \(f\) must be metric and BEP at the same time.
(a) The map \(f\) is metric.
Take an arbitrary edge \(\{a,b\}\in E(G)\). Proposition 2.1 asserts that it is enough to prove that the edge is mapped either to an edge or a vertex. Let \(G'\) be the connected component of \(G\) that contains \(\{a,b\}\). Observe that by Proposition 2.2, \(f(V(G'))\subset V(H')\) for some connected component \(H'\) in \(H\). \(H'\) must satisfy either of the \(3\) possibilities from the theorem’s statement. It is trivial to check that in all of them \(d_{H}(f(a),f(b))\leq 1\).
(b) The map \(f\) is BEP.
Fix an edge \(\{u,v\}\in V(H)\). Let \(H'\) be the connected component that contains \(\{u,v\}\). Since \(|V(H')|\geq2\), \(H'\) must satisfy either the first or the second condition. If it satisfies the first condition, \(f:V(G[f^{-1}(V(H'))])\to V(H')\) is an isomorphism, which means that \(f^{-1}(\{u,v\})\in E(G)\). If it satisfies the second condition, exactly one of the vertices \(u\) and \(v\) must belong to \(\mathop{\mathrm{Im}}_{2}{f}\) (the other has an empty pre-image). Suppose that it is \(u\): \(f^{-1}(\{u,v\})=f^{-1}(u)\). But it is also true that \(f^{-1}(u)\) is an isolated edge. Thus the pre-image of \(\{u,v\}\) is an edge, which implies that \(f\) is BEP. ◻
BEP homomorphisms can be described in a similar manner.
Proposition 3.6. A map \(f:V(G)\to V(H)\) between two (not necessarily connected) graphs \(G,H\) is a homomorphism and a BEP map at the same time if and only if \(f(\mathop{\mathrm{Iso}}(G))\subset\mathop{\mathrm{Iso}}(H)\) and the restriction of \(f\) to \(V(G)\setminus\mathop{\mathrm{Iso}}(G)\) is an isomorphism between \(G-\mathop{\mathrm{Iso}}(G)\) and \(H-\mathop{\mathrm{Iso}}(H)\).
Proof. Necessity. Suppose \(f\) is a homomorphism and a BEP map between \(G\) and \(H\). To show that \(f(\mathop{\mathrm{Iso}}(G))\subset\mathop{\mathrm{Iso}}(H)\), assume that there exists \(x\in\mathop{\mathrm{Iso}}(G)\) with \(f(x)\notin\mathop{\mathrm{Iso}}(H)\). Then there is \(y\in V(H)\) having \(\{y,f(x)\}\in E(H)\). But then \(f^{-1}(\{y,f(x)\})\notin E(G)\), which breaks the BEP condition.
Now let us prove that \(f\) induces an isomorphism between \(G-\mathop{\mathrm{Iso}}(G)\) and \(H-\mathop{\mathrm{Iso}}(H)\). Put \(g=f\big|_{V(G)\setminus\mathop{\mathrm{Iso}}{G}}\). Clearly, \(g\) remains both a homomorphism and a BEP map. We observe the following:
\(\bullet\) \(g\) is injective. Indeed, assume the existence of two distinct vertices \(u,v\in V(G)\setminus\mathop{\mathrm{Iso}}(G)\) with \(g(u)=g(v)\). Since \(u\) is not isolated in \(G\), we can pick a neighbor \(w\) of \(u\). Since \(g\) is a homomorphism, \(e=g(\{u,w\})\in E(H)\). If \(w=v\), then \(g(\{u,w\})=\{g(u)\}\), which is clearly not an edge. Thus, \(w\neq v\). But in this case, \(g^{-1}(e)\) contains at least \(3\) vertices: \(u,v,w\). This contradicts the fact that \(g\) is BEP.
\(\bullet\) \(g\) is surjective as a map onto \(H-\mathop{\mathrm{Iso}}(H)\). Suppose there exists a vertex \(h\in V(H)\setminus\mathop{\mathrm{Iso}}(H)\) with \(g^{-1}(h)=\emptyset\). Then given a neighbor \(t\) of \(h\), we see that \(|g^{-1}(\{h,t\})|\leq1\), which violates the injectivity.
\(\bullet\) \(g^{-1}\) is a homomorphism onto \(G-\mathop{\mathrm{Iso}}(G)\). This directly follows from the fact that \(g\) is BEP.
These observations, together with the fact that \(g\) is a homomorphism, lead to the conclusion that \(g\) is an isomorphism between \(G-\mathop{\mathrm{Iso}}(G)\) and \(H-\mathop{\mathrm{Iso}}(H)\).
Sufficiency. Suppose that \(f\) is a map between \(G\) and \(H\) that satisfies the conditions of the proposition. We now prove that \(f\) must be a homomorphism and BEP. As in the first part of the proof, we denote \(g=f\big|_{V(G)\setminus\mathop{\mathrm{Iso}}(G)}\).
To show that \(f\) is a homomorphism, take an arbitrary \(\{x,y\}\in E(G)\). It is apparent that \(x\) and \(y\) must belong to the domain of \(g\). But then they are isomorphically mapped onto \(H-\mathop{\mathrm{Iso}}(H)\), and their image must be an edge.
Now, let us verify that \(f\) is BEP. To see this, fix an edge \(e\in E(H)\). Similarly, \(e\in E(H-\mathop{\mathrm{Iso}}(H))\) implies \(f^{-1}(e)\in E(G)\). Therefore, \(f\) must be a BEP map. ◻
One natural generalization of BEP maps was already considered in [4].
A map \(f:V(G)\to V(H)\) between two graphs \(G,H\) is called a cohomomorphism if \(f^{-1}(e)\in E(G)\) for all \(e\in E(\mathop{\mathrm{Im}}{f})\).
It is clear from the definition that any BEP map is a cohomomorphism. However, cohomomorphisms form a much larger class of maps. For example, any map with an independent image is a cohomomorphism.
To characterize cohomomorphisms between graphs, we need a new notation. For a map \(f:V(G)\to V(H)\), define \[A(f)=\{u\in V(G):f(u)\notin\mathop{\mathrm{Iso}}(H[\mathop{\mathrm{Im}}{f}])\}.\]
In other words, \(A(f)\) is the pre-image of the set of all non-isolated vertices in the induced subgraph \(H[\mathop{\mathrm{Im}}{f}]\).
Proposition 3.7. A map \(f:V(G)\to V(H)\) between two (not necessarily connected) graphs \(G,H\) is a cohomomorphism if and only if it satisfies two conditions:
(a) the restriction of \(f\) to \(A(f)\) is injective;
(b) the inverse map \(f^{-1}:f(A(f))\to A(f)\) is a homomorphism between the corresponding induced subgraphs.
Proof. Necessity. Let \(u\in A(f)\). Then \(f(u)\) is not isolated in \(H[\mathop{\mathrm{Im}}{f}]\), implying the existence of a vertex \(v\in V(G)\) with \(\{f(u),f(v)\}\in E(H)\). Clearly, \(v\in A(f)\). Hence, the pre-image \(f^{-1}(f(u))\) is a singleton as \(f^{-1}(\{f(u),f(v)\})\in E(G)\) is an edge in \(G\). Hence, \(f\) must be injective on \(A(f)\). Further, if \(e\in E(f(A(f)))\) is an edge in \(f(A(f))\), then \(e=\{f(a),f(b)\}\) for some \(a,b\in A(f)\). Since \(f\) is a cohomomorphism, we have \(f^{-1}(e)=\{a,b\}\in E(G)\). Thus, \(f^{-1}\) is a homomorphism from \(H[f(A(f))]\) to \(G[A(f)]\).
Sufficiency. Let \(e\in E(\mathop{\mathrm{Im}}{f})\). Then \(e=\{f(u),f(v)\}\) for some \(u,v\in A(f)\). Since \(f\) is injective on \(A(f)\) and the corresponding inverse map \(f^{-1}\) is a homomorphism, we obtain \(f^{-1}(e)=\{u,v\}\in E(G)\). Therefore, \(f\) is a cohomomorphism. ◻
The next corollary characterizes cohomomorphisms in the class of homomorphisms.
Corollary 3.8. A map \(f:V(G)\to V(H)\) is a homomorphism and a cohomomorphism simultaneously if and only if \(f(\mathop{\mathrm{Iso}}(G))=\mathop{\mathrm{Iso}}(H[\mathop{\mathrm{Im}}{f}])\), and the restriction of \(f\) to \(V(G)\setminus\mathop{\mathrm{Iso}}(G)\) is an isomorphism onto its image.
Proof. Necessity. If \(f\) is a cohomomorphism, then the first condition from Proposition 3.7 implies that \(f(\mathop{\mathrm{Iso}}(G))\subset f(V(G)\setminus A(f))=\mathop{\mathrm{Iso}}(H[\mathop{\mathrm{Im}}{f}])\). To show that it is not a proper subset, suppose there exists an \(x\in V(G)\setminus\mathop{\mathrm{Iso}}(G)\) such that the image \(f(x)\) is an isolated vertex in \(H[\mathop{\mathrm{Im}}{f}]\). Then there is an edge \(\{x,a\}\in E(G)\) with \(f(x)\) and \(f(a)\) being non-adjacent in \(H\). This contradicts the fact that \(f\) is a homomorphism.
Further, since \(f\) is a homomorphism with \(f(V(G)\backslash\mathop{\mathrm{Iso}}(G))=f(A(f))\), the second condition from Proposition 3.7 asserts that the restriction of \(f\) to \(V(G)\backslash\mathop{\mathrm{Iso}}(G)\) is indeed an isomorphism between \(G-\mathop{\mathrm{Iso}}(G)\) and \(H[f(A(f))]\).
Sufficiency. Since \(f(\mathop{\mathrm{Iso}}(G))=\mathop{\mathrm{Iso}}(H[\mathop{\mathrm{Im}}{f}])\), we immediately obtain \(A(f)\subset V(G)\setminus\mathop{\mathrm{Iso}}(G)\). In fact, these sets are equal since the map \(f\) restricted to \(V(G)\setminus\mathop{\mathrm{Iso}}(G)\) provides an isomorphism onto its image. Thus, we can conclude that \(f\) is injective on \(A(f)\), and the inverse map \(f^{-1}\) from \(f(A(f))\) to \(A(f)\) establishes an isomorphism between \(H[f(A(f))]\) and \(G[A(f)]\). This means that \(f\) satisfies both conditions from Proposition 3.7. Hence, \(f\) is a homomorphism and a cohomomorphism at the same time. ◻
An example of a homomorphism and a cohomomorphism is given in Figure 2.
Corollary 3.9. Let \(G\) and \(H\) be connected graphs. A map \(f:V(G)\to V(H)\) is a homomorphism and a cohomomorphism simultaneously if and only if \(f\) is an isomorphism between \(G\) and \(H[\mathop{\mathrm{Im}}{f}]\).
Proof. Aside from \(K_{1}\) (the obvious case), connected graphs do not possess isolated vertices. Hence, Corollary 3.8 implies that for a map \(f\) being a homomorphism and a cohomomorphism at the same time is equivalent to \(f\) being an isomorphism between \(G\) and the subgraph in \(H\) induced by the image \(\mathop{\mathrm{Im}}{f}\). ◻
Note that any cohomomorphism can be viewed as a metric map from \(\overline{G}\) to \(\overline{H}\). However, the converse does not hold: consider the proper coloring \(f\) of a cycle \(C_{4}\) by the vertices of \(K_{2}\). Then \(f\) is a metric map between the complements \(\overline{C_{4}}=2K_{2}\) and \(\overline{K_{2}}\), but \(f\) is not a cohomomorphism. In Theorem 3.10, we will show that these classes of maps differ significantly, even within the class of homomorphisms.
Recall that two distinct vertices \(u,v\in V(G)\) are called false twins provided \(\{u,v\}\notin E(G)\) and \(N_{G}(u)=N_{G}(v)\). For a map \(f\colon X\to Y\), define \(R_{f}=\{(a,b)\in X^{2}:f(a)=f(b)\}\) to be the corresponding equivalence relation on \(X\) (called the kernel of \(f\)).
Theorem 3.10. For a map \(f:V(G)\to V(H)\), the following conditions are equivalent:
1. \(f\) is a homomorphism between \(G\), \(H\) and a metric map between \(\overline{G}\), \(\overline{H}\);
2. for all \(u,v\in V(G)\), the following condition holds: \(\{u,v\}\in E(G)\) if and only if \(\{f(u),f(v)\}\in E(H)\);
3. \(f\) satisfies two conditions:
\(\bullet\) for all \(u,v\in V(G)\) with \(f(u)=f(v)\), we have \(u=v\) or \(u,v\) are false twins;
\(\bullet\) \(f\) induces an isomorphism between the factor-graph \(G/{R_f}\) and \(H[\mathop{\mathrm{Im}}{f}]\).
Proof. \(1\Rightarrow 2\). Let \(\{u,v\}\in E(G)\). Then \(\{f(u),f(v)\}\in E(H)\) as \(f\) is a homomorphism. Conversely, if \(\{f(u),f(v)\}\in E(H)\), then \(f(u)\neq f(v)\) and \(\{f(u),f(v)\}\notin E(\overline{H})\). Since \(f\) is a metric map between \(\overline{G}\) and \(\overline{H}\), we conclude that \(\{u,v\}\notin E(\overline{G})\). And since \(u\neq v\) (as \(f(u)\neq f(v)\)), we deduce that \(\{u,v\}\in E(G)\).
\(2\Rightarrow 3\). Assume \(f(u)=f(v)\) for distinct \(u,v\in V(G)\). The second condition then implies that \(u\) and \(v\) are not adjacent in \(G\). Furthermore, let \(x\in N_{G}(u)\). Then \(\{f(x),f(u)\}\in E(H)\). However, \(\{f(x),f(u)\}=\{f(x),f(v)\}\), which implies that \(\{x,v\}\in E(G)\). Thus, \(x\in N_{G}(v)\). This means that \(N_{G}(u)\subset N_{G}(v)\). A similar argument would yield the other inclusion, hence, \(N_{G}(u)=N_{G}(v)\) meaning that \(u\) and \(v\) are false twins, as depicted in Figure 3.
Now, let us show that \(f\) indeed induces an isomorphism between \(G/{R_f}\) and \(H[\mathop{\mathrm{Im}}{f}]\). For any \([a]_{R_{f}}\in v(G)/{R_f}\), define \(\varphi([a]_{R_{f}})=f(a)\). It is clear that \(\varphi\) is a correctly defined map from \(v(G)/{R_f}\) to \(\mathop{\mathrm{Im}}{f}\). Moreover, \(\varphi\) is bijective. Further, let \(\{[a]_{R_{f}},[b]_{R_{f}}\}\in E(G/{R_f})\) be an edge in the factor-graph \(G/{R_f}\). Then there exist \(a'\in[a]_{R_{f}}\) and \(b'\in[b]_{R_{f}}\) with \(\{a',b'\}\in E(G)\). The second condition asserts that \(\varphi([a]_{R_{f}})=f(a)=f(a')\) is adjacent to \(\varphi([b]_{R_{f}})=f(b)=f(b')\) in \(H[\mathop{\mathrm{Im}}{f}]\). Conversely, if \(\varphi([a]_{R_{f}})\) and \(\varphi([b]_{R_{f}})\) are adjacent in \(H[\mathop{\mathrm{Im}}{f}]\), then so are \(f(a)\) and \(f(b)\). Hence, \(\{a,b\}\in E(G)\), which implies that there is an edge \(\{[a]_{R_{f}},[b]_{R_{f}}\}\in E(G/{R_f})\) in the factor-graph \(G/{R_f}\). Therefore, \(\varphi\) is an isomorphism.
\(3\Rightarrow 1\). Let \(\{u,v\}\in E(G)\). Then \(u\neq v\) and \(u,v\) are not false twins. Thus, the third condition asserts that \(f(u)\neq f(v)\). This means that the classes \([u]_{R_{f}}\) and \([v]_{R_{f}}\) are adjacent in \(G/{R_f}\). And since \(f\) induces an isomorphism between \(G/{R_f}\) and \(H[\mathop{\mathrm{Im}}{f}]\), the vertices \(f(u)\) and \(f(v)\) are adjacent in \(H\). This establishes that \(f\) is a homomorphism between \(G,H\).
Finally, let \(\{u,v\}\in E(\overline{G})\). Assume that \(f(u)\) is adjacent to \(f(v)\) in \(H\). Then \(\varphi(u)\) is adjacent to \(\varphi(v)\) in the corresponding factor-graph. This means that there exist \(u'\in[u]_{R_{f}}\) and \(v'\in[v]_{R_{f}}\) with \(\{u',v'\}\in E(G)\).
By the first part of the third condition, we have the next four possibilities: \(u=u'\) and \(v=v'\); \(u=u'\) and \(v\), \(v'\) are false twins; \(u\), \(u'\) are false twins and \(v=v'\); \(u\), \(u'\) and \(v\), \(v'\) are two pairs of false twins.
If \(u=u'\) and \(v=v'\), then \(\{u,v\}\in E(G)\). Now, assume \(u=u'\) and \(v\), \(v'\) are false twins. Then \(\{u,v'\}\in E(G)\), implying that \(\{u,v\}\in E(G)\). Similarly, if \(u\), \(u'\) are false twins and \(v=v'\), then also \(\{u,v\}\in E(G)\). Finally, let \(u\), \(u'\) and \(v\), \(v'\) be two pairs of false twins. Then again, the existence of an edge \(\{u',v'\}\in E(G)\) implies that \(\{u',v\}\in E(G)\), which in turn yields \(\{u,v\}\in E(G)\). In all cases, we obtain a contradiction.
Hence, \(f(u)=f(v)\) or \(\{f(u),f(v)\}\in E(\overline{H})\). This means that \(f\) is a metric map between \(\overline{G}\), \(\overline{H}\). ◻
Note that if \(f\colon V(G)\to V(H)\) is a homomorphism and a cohomomorphism simultaneously, then Corollary 3.8 immediately implies that the equality \(f(x)=f(y)\) is only possible if \(x=y\) or \(x,y\) are both isolated vertices in \(G\). In the last case, \(x\) and \(y\) are false twins. Also, the fact that the restriction of \(f\) to \(V(G)\setminus\mathop{\mathrm{Iso}}(G)\) gives an isomorphism from \(G-\mathop{\mathrm{Iso}}(G)\) onto its image asserts that \(f\) induces an isomorphism between the factor-graph \(G/{R_f}\) and \(H[\mathop{\mathrm{Im}}{f}]\). Therefore, \(f\) satisfies the third condition of Theorem 3.10, implying that \(f\) is a metric map between complements \(\overline{G}\), \(\overline{H}\).
Given two equivalence relations \(R,Q\) on a set \(X\), we say the relation \(R\) is finer than \(Q\) provided \(R\subset Q\).
Corollary 3.11. For graphs \(G\) and \(H\), there exists a homomorphism \(f:V(G)\to V(H)\) which is a metric map between their complements if and only if there is an equivalence relation \(R\) on \(V(G)\) such that \(R\) is finer than the relation of “being equal or being false twins”, and the factor-graph \({G}/{R}\) is isomorphic to an induced subgraph in \(H\).
Proof. Necessity. This clearly follows from Theorem 3.10.
Sufficiency. Let \(R\) be the mentioned equivalence relation \(V(G)\). By \(\pi:V(G)\to V(G)/{R}\) denote the corresponding projection map. Further, fix an isomorphism \(\varphi\) between \({G}/{R}\) and some induced subgraph in \(H\). Consider the composition \(f=\varphi\circ\pi\colon V(G)\to V(H)\). It is clear that \(f\) satisfies the third condition from Theorem 3.10. Hence, \(f\) is a homomorphism between \(G\), \(H\) as well as a metric map between their complements. ◻
The authors are deeply grateful to the Armed Forces of Ukraine for keeping Kyiv safe during the work on this paper. Special thanks are extended to Bohdan-Yarema Dekhtiar for proofreading the manuscript and providing valuable suggestions.