📂Graph Theory

Graph Homomorphism

Definition ¹

Given two graphs $G_{1}$ and $G_{2}$, if there exists a graph isomorphism between some subdivision $G_{1} ' $ of $G_{1}$ and some subdivision $G_{2} ' $ of $G_{2}$, then $G_{1}$ and $G_{2}$ are said to be homeomorphic.

---

• A graph $G$ with vertices $w$ added in succession that satisfy the following condition is called the subdivision $G'$ of $G$. $$ \begin{align*} u \sim_{G} v & \implies \begin{cases} u \nsim_{G'} v \\ u \sim_{G'} w \\ w \sim_{G'} v \\ \deg w = 2 \end{cases} \end{align*} $$
• $x \sim_{A} y$ infers that two vertices $x,y$ in graph $A$ are adjacent.

Explanation

Simply put, it refers to the graph with $w$ added between edges that were connected in the original graph. The following image makes it easier to understand.

The two graphs on the right show two examples of subdivisions of the graph $G$ given on the left. The added vertex does not necessarily have to be one and can be inserted into the same edge simultaneously.

Here is an example of two homeomorphic graphs.

Looking at such subdivisions, it can be confirmed that the straight-through connection in the original graph remains unchanged whether or not vertices are added. Using this concept, it can be said that the following two graphs are essentially the same. Graph homeomorphism deals with spatial sameness, unlike graph isomorphism, which is about exact structural identity. The term itself also comes from homeomorphism in topology.

See Also

• Homeomorphism in Topology
• Graph Isomorphism