Acquaintance time of random graphs near connectivity threshold

DOI10.1137/140969105zbMATH Open1333.05271arXiv1405.3252OpenAlexW2963635656MaRDI QIDQ2801332FDOQ2801332

Authors: Andrzej Dudek, Paweł Prałat 

Publication date: 7 April 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Benjamini, Shinkar, and Tsur stated the following conjecture on the acquaintance time: asymptotically almost surely $AC(G)le{p}^{-1}lo{g}^{O(1)}n$ for a random graph $GinG(n,p)$, provided that $G$ is connected. Recently, Kinnersley, Mitsche, and the second author made a major step towards this conjecture by showing that asymptotically almost surely $AC(G)=O(logn/p)$, provided that $G$ has a Hamiltonian cycle. In this paper, we finish the task by showing that the conjecture holds in the strongest possible sense, that is, it holds right at the time the random graph process creates a connected graph. Moreover, we generalize and investigate the problem for random hypergraphs.

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

Recommendations

• A note on the acquaintance time of random graphs
• The acquaintance time of (percolated) random geometric graphs
• A tight upper bound on acquaintance time of graphs
• Acquaintance time of a graph
• Rapid social connectivity

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) Connectivity (05C40) Games on graphs (graph-theoretic aspects) (05C57) Hypergraphs (05C65) Games involving graphs (91A43)

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?)
• Title not available (Why is that?)
• Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs
• Loose Hamilton cycles in random uniform hypergraphs
• Loose Hamilton cycles in random 3-uniform hypergraphs
• The acquaintance time of (percolated) random geometric graphs
• Acquaintance time of a graph
• A note on the acquaintance time of random graphs
• Routing Permutations on Graphs via Matchings
• New bounds for contagious sets
• The longest path in a random graph
• Long paths and cycles in random subgraphs of graphs with large minimum degree

Cited In (6)

• The acquaintance time of (percolated) random geometric graphs
• Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
• A tight upper bound on acquaintance time of graphs
• Collision-free network exploration
• A note on the acquaintance time of random graphs
• Acquaintance time of a graph

This page was built for publication: Acquaintance time of random graphs near connectivity threshold

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