A note on the acquaintance time of random graphs

MaRDI QIDQ396895zbMATH OpenFDO

Authors William B. Kinnersley, D. Mitsche, Paweł Prałat

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.1675, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p52

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

random graphsvertex-pursuit gamesacquaintance time

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Games on graphs (graph-theoretic aspects) (05C57)

Abstract: In this short note, we prove the conjecture of Benjamini, Shinkar, and Tsur on the acquaintance time $AC(G)$ of a random graph $GinG(n,p)$. It is shown that asymptotically almost surely $AC(G)=O(logn/p)$ for $GinG(n,p)$, provided that $pn>(1+epsilon)logn$ for some $epsilon>0$ (slightly above the threshold for connectivity). Moreover, we show a matching lower bound for dense random graphs, which also implies that asymptotically almost surely $K_n$ cannot be covered with $o(logn/p)$ copies of a random graph $GinG(n,p)$, provided that $pn>n^{1/2+epsilon}$ and $p<1-epsilon$ for some $epsilon>0$. We conclude the paper with a small improvement on the general upper bound showing that for any $n$-vertex graph $G$, we have $AC(G)=O(n^2/logn)$.

Recommendations

• Acquaintance time of random graphs near connectivity threshold
• The acquaintance time of (percolated) random geometric graphs
• A tight upper bound on acquaintance time of graphs
• Acquaintance time of a graph
• scientific article; zbMATH DE number 2079333

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A survey of gossiping and broadcasting in communication networks
• A tight upper bound on acquaintance time of graphs
• Acquaintance time of a graph
• New bounds for contagious sets
• On the approximability of influence in social networks
• Random graphs.
• Routing Permutations on Graphs via Matchings
• The acquaintance time of (percolated) random geometric graphs

Cited in

(5)

• The acquaintance time of (percolated) random geometric graphs
• Acquaintance time of random graphs near connectivity threshold
• A tight upper bound on acquaintance time of graphs
• Collision-free network exploration
• Acquaintance time of a graph

This page was built for publication: A note on the acquaintance time of random graphs

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