What does Graph epimorphism mean? Does that implies a surjective homomorphism (A mapping between graphs that preserves their structure) of graphs? Can you please explain it?


An epimorphism from G to H is a surjective function $f : V(G) → V(H)$ such that

$\forall$ $u,v ∈ V(G)$ ,if $(u,v)∈A(G)$,then $(f(u),f(v))∈A(H)$ (graph homomorphism)

$\forall$ $(u′, v′) ∈ A(H)$, there exists $(u, v) ∈ A(G)$ such that $f (u) = u′$ and $f (v) = v′$ (surjectivity on arcs) i.e., every node in H is an image of some node in G. .

Hence we call $f$ an $Epimorphism$ if every node or arc in $H$ is image of a vertex or arc in $G$.

  • 1
    $\begingroup$ Okay. I couldn't understand what A(H), A(G) represents here. Can you please explain a bit more about this set? Does that mean the set of adjacent pairs of vertices of a graph? $\endgroup$ – Kavita Jan 14 at 18:01
  • $\begingroup$ Yes they are sets of adjacent pairs of vertices. I assumed $G$ and $H$ are directed graphs, therefore $A$ is set of arcs(directed edges). However, we can use the word $E$ instead of $A$. $\endgroup$ – W.R.P.S Jan 14 at 18:51
  • 1
    $\begingroup$ Okay. got it..Thank you!! $\endgroup$ – Kavita Jan 14 at 18:59
  • $\begingroup$ I have a question. In this definition, we have surjectivity on arcs. Why not just surjectivity on vertices? Is there any other definition of surjective graph homomorphism which is different from graph epimorphism or both implies the same thing? Also, can you please suggest some reference book/links to understand this concept thoroughly? $\endgroup$ – Kavita Jan 30 at 11:52
  • $\begingroup$ Definition of surjective homomorphism with surjectivity on edges is stronger than just surjectivity on vertices Golovach, Petr A., et al. "Finding vertex-surjective graph homomorphisms.. Graph Compaction is a surjective graph homomorphism with surjectivity on edges, but compaction does not require covering the loops-of the graph $H$ whereas the epimorphism requires covering the loops of the graph $H$ Vikas, Narayan. Computational complexity of graph compaction.1997.. $\endgroup$ – W.R.P.S Jan 31 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.