Article ID Journal Published Year Pages File Type
6872194 Discrete Applied Mathematics 2014 7 Pages PDF
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
,