Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419683 | Discrete Applied Mathematics | 2013 | 9 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Timothy D. LeSaulnier, Douglas B. West,