Geodesic
The Total Acquisition Number Of The Randomly Weighted Path
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 4, pp. 919-934.

Voir la notice de l'article provenant de la source Library of Science

There exists a significant body of work on determining the acquisition number at(G) of various graphs when the vertices of those graphs are each initially assigned a unit weight. We determine properties of the acquisition number of the path, star, complete, complete bipartite, cycle, and wheel graphs for variations on this initial weighting scheme, with the majority of our work focusing on the expected acquisition number of randomly weighted graphs. In particular, we bound the expected acquisition number E(at(Pn)) of the n-path when n distinguishable “units” of integral weight, or chips, are randomly distributed across its vertices between 0.242n and 0.375n. With computer support, we improve it by showing that E(at(Pn)) lies between 0.29523n and 0.29576n. We then use subadditivity to show that the limiting ratio lim E(at(Pn))/n exists, and simulations reveal more exactly what the limiting value equals. The Hoeffding-Azuma inequality is used to prove that the acquisition number is tightly concentrated around its expected value. Additionally, in a different context, we offer a non-optimal acquisition protocol algorithm for the randomly weighted path and exactly compute the expected size of the resultant residual set.
Keywords: total acquisition number, Poissonization, dePoissonization, Maxwell-Boltzman and Bose-Einstein allocation 
@article{DMGT_2017_37_4_a4,
     author = {Godbole, Anant and Kelley, Elizabeth and Kurtz, Emily and Pra{\l}at, Pawe{\l} and Zhang, Yiguang},
     title = {The {Total} {Acquisition} {Number} {Of} {The} {Randomly} {Weighted} {Path}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {919--934},
     publisher = {mathdoc},
     volume = {37},
     number = {4},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a4/}
}
TY  - JOUR
AU  - Godbole, Anant
AU  - Kelley, Elizabeth
AU  - Kurtz, Emily
AU  - Prałat, Paweł
AU  - Zhang, Yiguang
TI  - The Total Acquisition Number Of The Randomly Weighted Path
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 919
EP  - 934
VL  - 37
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a4/
LA  - en
ID  - DMGT_2017_37_4_a4
ER  - 
%0 Journal Article
%A Godbole, Anant
%A Kelley, Elizabeth
%A Kurtz, Emily
%A Prałat, Paweł
%A Zhang, Yiguang
%T The Total Acquisition Number Of The Randomly Weighted Path
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 919-934
%V 37
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a4/
%G en
%F DMGT_2017_37_4_a4
Godbole, Anant; Kelley, Elizabeth; Kurtz, Emily; Prałat, Paweł; Zhang, Yiguang. The Total Acquisition Number Of The Randomly Weighted Path. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 4, pp. 919-934. http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a4/

[1] D. Bal, P. Bennett, A. Dudek and P. Pra lat, The total acquisition number of random graphs (2016), arXiv:1402.2854.

[2] E. Czabarka, M. Marsili and L.A. Székely, Threshold functions for distinct parts: revisiting Erd˝os-Lehner, in: Information Theory, Combinatorics, and Search Theory (in Memory of Rudolph Ahlswede), H. Aydinian, F. Cicalese and C. Deppe (Eds.), Springer-Verlag, Lecture Notes in Comput. Sci. 7777 (2013) 463-471. doi: 10.1007/978-3-642-36899-8 22

[3] D.E. Lampert and P.J. Slater, The acquisition number of a graph, Congr. Numer. 109 (1995) 203-210.

[4] T. LeSaulnier, N. Prince, P. Wenger, D. West and P. Worah, Total acquisition in graphs, SIAM J. Discrete Math. 27 (2013) 1800-1819. doi: 10.1137/110856186

[5] P. Wenger, Fractional acquisition in graphs, Discrete Appl. Math. 178 (2014) 142-148. doi: 10.1016/j.dam.2014.06.010

[6] D. West, N. Prince and P. Wenger, Unit acquisition in graphs, preprint.

[7] P. Pra lat, C++ program and results can be found at http://www.math.ryerson.ca/˜pralat/.