Neighborhood contraction in graphs
type: Item
instance of: scholarly article
title: Neighborhood contraction in graphs
zbMATH Open document ID: 1404.05181
author: S. S. Kamath
author: Prameela Kolake
published in: Indian Journal of Pure \& Applied Mathematics
publication date: 2018-11-07T00:00:00Z
review text: 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.
reviewed by: Sergiy Kozerenko
Mathematics Subject Classification ID: 05C76
Mathematics Subject Classification ID: 05C83
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 6974454
zbMATH Keywords: neighborhood
zbMATH Keywords: degree
zbMATH Keywords: induced subgraph
zbMATH Keywords: contraction
zbMATH Keywords: domination
MaRDI profile type: Publication
full work available at URL: s13226-015-0169-9
OpenAlex ID: W2226814487
cites work: Contraction and Treewidth Lower Bounds
cites work: Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
cites work: Q4368728
cites work: Some recent progress and applications in graph minor theory
cites work: Graph minor theory
DOI: 10.1007/S13226-015-0169-9
description: scientific article; zbMATH DE number 6974454