0
$\begingroup$

Let G be a graph that contains at least one connected subset of vertices.

Let S be a connected subset of vertices of G.

Let G[S] denote the induced subgraph of S in G.

Let's consider an operation that transforms G to another graph G' by contracting all the edges of G[S].

Informally speaking, it consists of "condensing" or "contracting" G[S] to one vertex (always possible as S is connected), while conserving all the edges that connect a vertex in S to a vertex outside of S.

Is there a particular name used to call such a type of operation? May one say this is the contraction of S in G, or is there any other more appropriate term, if any?

Supplementary question: Is there a particular name used to call the relationship between G and G'?

$\endgroup$
1
  • $\begingroup$ Welcome to MSE! Let me know if there's an itch my answer doesn't scratch. $\endgroup$
    – user20672
    Commented Apr 7, 2021 at 11:25

1 Answer 1

1
$\begingroup$

This is called a quotient map in other contexts, and I would write it as $G/S$ to indicate that I've used an equivalence relation to identify all vertices in $S$, or $G/{\sim}$ if instead I specify an equivalence relation denoted ${\sim}$.

It seems graph theory has this same notion (see here). Given the context in which quotient maps arise in mathematics, namely topology, it makes sense that graph theorists would use the same notation; graphs are a commonly studied topology.

In particular, it seems a condensation is a specific type of quotient graph related to what you're curious to know more about. A condensation is when each strongly connected component is treated as a single vertex.

As for what to call $G/S$? In topology, you might see it called the quotient space; in graph theory, it seems it is called the quotient graph.

PS there is a related notion in topology called a deformation retract, which you can read about here. Unfortunately, that Wiki article is pretty bad in my opinion. Instead, I like Hatcher's treatment. You can find a PDF of his book here. The section on deformation retracts is short. A more basic topology book, like Monkres, would provide a good discussion of quotient maps and quotient spaces, but maybe this is more detailed than what you wanted to know.

$\endgroup$

You must log in to answer this question.

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