The total acquisition number of the randomly weighted path

DOI10.7151/DMGT.1972MaRDI QIDQ2409784zbMATH OpenOpenAlexFDO

Authors Anant P. Godbole, Elizabeth Kelley, Emily Kurtz, Paweł Prałat, Yiguang Zhang

Publication date 13 October 2017

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1507.06019

zbMATH Keywords

poissonizationdepoissonizationtotal acquisition numberBose-Einstein allocationMaxwell-Boltzman allocation

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Abstract: There exists a significant body of work on determining the acquisition number $a_t(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(a_t(P_n))$ 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(a_t(P_n))$ lies between $0.29523n$ and $0.29576n$. We then use subadditivity to show that the limiting ratio $limE(a_t(P_n))/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.

Recommendations

• The total acquisition number of random graphs
• scientific article; zbMATH DE number 2170474
• The total acquisition number of random geometric graphs
• Total Path Length for Random Recursive Trees
• The unit acquisition number of binomial random graphs
• The optimal path in an Erdős-Rényi random graph
• The Distribution of Path Lengths On Directed Weighted Graphs
• scientific article; zbMATH DE number 1185306
• Successive shortest paths in complete graphs with random edge weights
• Shortest paths in random weighted graphs

Cites work

• scientific article; zbMATH DE number 1185306 (Why is no real title available?)
• Fractional acquisition in graphs
• The total acquisition number of random graphs
• Threshold functions for distinct parts: revisiting Erdős-Lehner
• Total acquisition in graphs

Cited in

(5)

• The unit acquisition number of a graph
• Weighted total acquisition
• The total acquisition number of random geometric graphs
• The total acquisition number of random graphs
• The unit acquisition number of binomial random graphs

This page was built for publication: The total acquisition number of the randomly weighted path

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409784)