Let $G,H$ be graphs with at most one edge between vertices, with loops allowed. A homomorphism of graphs from $G$ to $H$ is a vertex mapping $f\colon V(G)\to V(H)$ such that if $\{u,v\}$ is an edge of $G$, then $\{f(u),f(v)\}$ is an edge of $H$.

I my research, I need a name for a somewhat more general notion: a vertex mapping $f\colon V(G)\to V(H)$ such that if $\{u,v\}$ is an edge of $G$, then either $f(u)=f(v)$ or $\{f(u),f(v)\}$ is an edge. So every edge of $G$ is either mapped to an edge or contracted to a vertex.

Question: Is there (at least a semi-standard) name of such mappings between graphs?

I am aware that this terminological problem commonly solved/handwaved by putting loops on every vertex. However, in my case I need to consider both types of morphisms at the same time, so I cannot do this.


1 Answer 1


I'm not a graph theorist so I can't give you any advice on terminology. But I can offer a different point of view. How about being explicit about the category in which your morphisms live? Two options for embedding the category of graphs without loops come to my mind:

(1) The, so called, category of simple graphs has been suggested on ncatlab to tackle precisely the same issue. They model graphs as sets equipped with a symmetric reflexive relation. Since every vertex has a loop, you're encoding the same amount of information.

(2) Another option might be to embed the category of graphs without loops $\mathbb G$ to the category $\mathbb G^+$ of graphs which possibly can have loops (but do not have to). Then, you have a monad $T\colon \mathbb G^+ \to \mathbb G^+$ which adds all missing loops (I hope that this is a monad :-)). Then your morphisms are just Kleisli morphisms $A \to T(B)$ where $A$ and $B$ are without loops.

The advantage of the second option is that you can still recover the original subcategory $\mathbb G$ within $\mathbb G^+$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .