The total acquisition number of the randomly weighted path

DOI10.7151/DMGT.1972zbMATH Open1372.05180arXiv1507.06019OpenAlexW2964175400MaRDI QIDQ2409784FDOQ2409784

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)

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.

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

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
• Successive shortest paths in complete graphs with random edge weights
• Shortest paths in random weighted graphs

zbMATH Keywords

poissonizationdepoissonizationtotal acquisition numberBose-Einstein allocationMaxwell-Boltzman allocation

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Cites Work

• Title not available (Why is that?)
• Total Acquisition in Graphs
• Fractional acquisition in graphs
• Threshold Functions for Distinct Parts: Revisiting Erdős–Lehner
• The total acquisition number of random graphs

Cited In (4)

• The unit acquisition number of a graph
• Weighted total acquisition
• The total acquisition number of random geometric 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)