I want to study a graph $\mathcal G=(\mathcal V,\mathcal E)$, which emerges from a simple graph $G=(V,E)$ by considering certain vertex sets in $G$ as single vertices. In detail: I choose a partition $V_1\,\dot\cup\,\cdots\,\dot\cup\, V_n=V$ and define

$$\mathcal V=\{V_1,...,V_n\},\qquad \mathcal E=\{\{V_1,V_2\}\mid \text{$E$ contains an edge between $V_1$ and $V_2$}\}.$$

To me, $\mathcal G$ looks like a graph minor of $G$, but 1) we can contract also edges which are not there, 2) I am not allowed to delete edges. Is there a term for such a process or such a graph $\mathcal G$ (cluster graph, block graph, ...)?

  • $\begingroup$ If each subgraph $V_j$ is connected, this is the same thing as contracting all edges in $V_j$ and removing loops and multiedges. $\endgroup$
    – N. S.
    Mar 28 '18 at 16:34
  • $\begingroup$ Replacing any one set of vertices with a single vertex (and collapsing multiple edges into a single edge) is call vertex identification (or vertex contraction) $\endgroup$
    – Joffan
    Apr 2 '18 at 21:29

The term you are looking for is Quotient Graph.


I would like to point out that this kind of construction is more general. As has been pointed out, this is a quotient graph.

In topology, if you have a topological space, you can create a new space by considering some points in the space to be the same. (For example, if you have $[0,1]$ with standard subspace topology, then you form a new space, say by considering $0$ and $1$ to be the same. This will be homeomorphic to a circle $S^1$)

In abstract algebra, you can often take quotients on your structure, which will amount to thinking of different elements as the same (here you have to be careful about how you do this). For example, if you have a group and a normal subgroup, then you can get a quotient group where the cosets are the group elements. You can think of these cosets as the equivalence classes.


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.