Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654404 | European Journal of Combinatorics | 2009 | 12 Pages |
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
Marc Comas, Maria Serna,