Article ID Journal Published Year Pages File Type
419683 Discrete Applied Mathematics 2013 9 Pages PDF
Abstract

A total acquisition move   in a weighted graph GG moves all weight from a vertex uu to a neighboring vertex vv, provided that before this move the weight on vv is at least the weight on uu. The total acquisition number  , at(G)at(G), is the minimum number of vertices with positive weight that remain in GG after a sequence of total acquisition moves, starting with a uniform weighting of the vertices of GG. For n≥2n≥2, Lampert and Slater showed that at(G)≤n+13 when GG has nn vertices, and this is sharp. We characterize the graphs achieving equality: at(G)=∣V(G)∣+13 if and only if G∈T∪{P2,C5}G∈T∪{P2,C5}, where TT is the family of trees that can be constructed from P5P5 by iteratively growing paths with three edges from neighbors of leaves.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,