TOPICS
Search

Vertex Contraction


The contraction of a pair of vertices v_i and v_j of a graph, also called vertex identification, is the operation that produces a graph in which the two nodes v_1 and v_2 are replaced with a single node v such that v is adjacent to the union of the nodes to which v_1 and v_2 were originally adjacent. In vertex contraction, it doesn't matter if v_1 and v_2 are connected by an edge; if they are, the edge is simply removed upon contraction (Pemmaraju and Skiena 2003, p. 231). Note that Skiena (1990, p. 91) is ambiguous about the distinction between vertex contraction and edge contraction, and confusingly refers to vertex contraction on vertices v_1 and v_2 as "contracting an edge {v_1,v_2}."

GraphContraction

The figure above shows a random graph contracted on vertices v_7 and v_9.

Vertex contraction is implemented in the Wolfram Language as VertexContract[g, {v1, v2, ...}].


See also

Edge Contraction

Explore with Wolfram|Alpha

References

Pemmaraju, S. and Skiena, S. "Contracting Vertices." §6.1.1 in Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, pp. 231-234, 2003.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 91, 1990.

Referenced on Wolfram|Alpha

Vertex Contraction

Cite this as:

Weisstein, Eric W. "Vertex Contraction." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/VertexContraction.html

Subject classifications