Acquaintance Time of Random Graphs Near Connectivity Threshold

DOI10.1137/140969105zbMath1333.05271arXiv1405.3252OpenAlexW2963635656MaRDI QIDQ2801332

Andrzej Dudek, Paweł Prałat

Publication date: 7 April 2016

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

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

zbMATH Keywords

random graphsvertex-pursuit gamesacquaintance time

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (3)

A tight upper bound on acquaintance time of graphs ⋮ Collision-free network exploration ⋮ The acquaintance time of (percolated) random geometric graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the acquaintance time of random graphs
• New bounds for contagious sets
• Loose Hamilton cycles in random uniform hypergraphs
• Loose Hamilton cycles in random 3-uniform hypergraphs
• The longest path in a random graph
• Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs
• The acquaintance time of (percolated) random geometric graphs
• Acquaintance Time of a Graph
• On the Approximability of Influence in Social Networks
• A survey of gossiping and broadcasting in communication networks
• Routing Permutations on Graphs via Matchings
• Long paths and cycles in random subgraphs of graphs with large minimum degree

This page was built for publication: Acquaintance Time of Random Graphs Near Connectivity Threshold