Previously asked on MSE.

Given a simple graph $G=(V,E)$ and an edge $uv\in E$, the contraction of $uv$ refers to the replacement of the vertices $u$ and $v$ with a new vertex $w$ such that the edges incident on $w$ correspond to the ones that were incident on either $u$ or $v$. Edge contraction comes up in the study of graph minors.

Consider a similar operation: remove the edge $uv$, but not the vertices, and add a new vertex $w$ such that the edges incident on $w$ correspond to the ones other than $uv$ that are incident on either $u$ or $v$.

Does this graph operation have a name or has it ever come up in the literature?

Background. This came up as I was exploring how the Resolution graph of a CNF formula evolves if we try to express each step of a given Resolution proof as an operation on the graph. For a CNF formula, its Resolution graph includes each clause as a vertex and an edge between two vertices if there exists a unique variable that their corresponding clauses can be resolved with respect to. Resolving two clauses corresponds to performing the operation I described, followed potentially by some edge deletions. I was wondering if there exist interesting graph invariants that are monotone with respect to the operation I described (somewhat similar to minor-monotone invariants).



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.