Neighborhood contraction in graphs (Q1616737)

Similarly to edge contraction, the authors define an operation of the neighborhood contraction at a given vertex in a graph. It is proved that at most \(\lfloor\frac{n}{2}\rfloor\) neighborhood contractions are needed in order to reduce a given \(n\)-vertex graph to the trivial graph. The criterion for an isomorphism between the neighborhood contraction of a graph and the neighborhood contraction of its complement at a given vertex, is provided. The paper also contains results on neighborhood contractions in some special graph classes including bipartite graphs, trees and regular graphs. Finally, the authors study the behavior of dominating properties in graphs under the neighborhood contraction operation.