Article ID Journal Published Year Pages File Type
4654404 European Journal of Combinatorics 2009 12 Pages PDF
Abstract

In this paper, we analyze parameter improvement under vertex fusion in a graph GG. This is a setting in which a new graph G′G′ is obtained after identifying a subset of vertices of GG in a single vertex. We are interested in distance parameters, in particular diameter, radius and eccentricity of a vertex vv. We show that the corresponding problem is NP-Complete for the three parameters. We also find graph classes in which the problem can be solved in polynomial time.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,