Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6872194 | Discrete Applied Mathematics | 2014 | 7 Pages |
Abstract
Let G be a vertex-weighted graph in which each vertex has weight 1. Given a vertex u with positive weight and a neighbor v whose weight is at least the weight on u, a fractional acquisition move transfers some amount of weight at u from u to v. The fractional acquisition number of G, written af(G), is the minimum number of vertices with positive weight after a sequence of fractional acquisition moves in G. In this paper, we determine the fractional acquisition number of all graphs: if G is an n-vertex path or cycle, then af(G)=ân/4â; if G is connected with maximum degree at least 3, then af(G)=1.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Paul S. Wenger,