The unit acquisition number of binomial random graphs (Q2048570): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / arXiv ID | |||
Property / arXiv ID: 2006.13294 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3503433 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The total acquisition number of random graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast Gossiping by Short Messages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3546603 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Broadcasting in random graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Close-to-optimal and near-optimal broadcasting in random graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The total acquisition number of the randomly weighted path / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A survey of gossiping and broadcasting in communication networks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The total acquisition number of random geometric graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4519896 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3838202 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Total Acquisition in Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Acquisition-extremal graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2875489 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The unit acquisition number of a graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3507250 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4677970 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fractional acquisition in graphs / rank | |||
Normal rank |
Latest revision as of 09:23, 26 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The unit acquisition number of binomial random graphs |
scientific article |
Statements
The unit acquisition number of binomial random graphs (English)
0 references
9 August 2021
0 references
Summary: Let \(G\) be a graph in which each vertex initially has weight 1. In each step, the unit weight from a vertex \(u\) to a neighbouring vertex \(v\) can be moved, provided that the weight on \(v\) is at least as large as the weight on \(u\). The unit acquisition number of \(G\), denoted by \(a_u(G)\), is the minimum cardinality of the set of vertices with positive weight at the end of the process (over all acquisition protocols). In this paper, we investigate the Erdős-Rényi random graph process \((\mathcal{G}(n,m))_{m =0}^N \), where \(N = \binom{n}{2}\). We show that asymptotically almost surely \(a_u(\mathcal{G}(n,m)) = 1\) right at the time step the random graph process creates a connected graph. Since trivially \(a_u(\mathcal{G}(n,m)) \geqslant 2\) if the graphs are disconnected, the result holds in the strongest possible sense.
0 references
information dissemination
0 references
total acquisition move
0 references
total acquisition number
0 references