A note on the acquaintance time of random graphs

zbMATH Open1295.05210arXiv1305.1675MaRDI QIDQ396895FDOQ396895

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)

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)$.

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

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

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

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)

Cites Work

• Title not available (Why is that?)
• Random graphs.
• On the approximability of influence in social networks
• A survey of gossiping and broadcasting in communication networks
• Title not available (Why is that?)
• The acquaintance time of (percolated) random geometric graphs
• Acquaintance time of a graph
• A tight upper bound on acquaintance time of graphs
• Routing Permutations on Graphs via Matchings
• New bounds for contagious sets

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)