graph homomorphism

[[concept]]

Graph Homomorphism

Let $G=(V,E)$ and $F=(V^{\prime },E^{\prime })$. A graph homomorphism from $F$ to $G$ is a map $\gamma :F\to G$ such that $(i,j)\in E^{\prime }⟹(\gamma (i),\gamma (j))\in E^{\prime }$ ie, homomorphisms are adjacency-preserving maps (of $F$; the adjacency of $F$ must be preserved in $G$.)

Exercise

How is a homomorphism not the same as a graph isomorphism?

Answer

Recall the definition of the isomorphism

Graph Isomorphism $G$ and $G^{\prime }$ be two graphs. A graph isomorphism between $G$ and $G^{\prime }$ is a bijection $M:V(G)\to V(G^{\prime })$ such that for all $i,j\in V(G)$ $(i,j) \in E(G) \iff(M(i), M(j)) \in E(G')$$

Let

The isomorphism requires that both graphs share all edges. The homomorphism requires that the second graph, $G$, is a subgraph of the first, $F$.

We also define

Homomorphism Count

We denote $\text{hom}(F,G)$ as the total number of homomorphisms from $F$ to $G$.

Example

There are a few homomorphisms from $F$ to $G$:

• $(a,b,c)\mapsto (1,2,3)$
  • And trivially, every permutation of $(a,b,c)$ is also a homomorphism here

There are also:

• $(a,b,c)\mapsto (1,2,4)$
• $(a,b,c)\mapsto (1,3,4)$
• $(a,b,c)\mapsto (2,3,4)$ and for each of the above, each permutation of $(a,b,c)$ as well.

The homomorphism count $\text{hom}(F,G)=24$ in this case.

---

Review

dsg

Q: If $F$ is a (graph) isomorphism of $G$, how is this different from a homomorphism? -?- A: The isomorphism requires that both graphs share all edges. The homomorphism requires that the second graph, $F$, is a subgraph of the first, $G$.

graph homomorphisms are {-adjacency-preserving maps-} (of $F$ in $G$)

References

Mentions

TABLE
FROM [[]]
 
FLATTEN choice(contains(artist, this.file.link), 1, "") + choice(contains(author, this.file.link), 1, "") + choice(contains(director, this.file.link), 1, "") + choice(contains(source, this.file.link), 1, "") as direct_source
 
WHERE !direct_source