ABSTRACT
The problem of determining the acquaintance time is related to problems of routing permutations on graphs via matchings, gossiping and broadcasting, and target set selection. This chapter examines the acquaintance time of other models of random graphs, such as power-law graphs, preferential attachments graphs, or geometric graphs. The desired bound for the acquaintance time holds at the time a random graph becomes Hamiltonian. The chapter shows that the conjecture holds above the threshold for connectivity by considering sparse random graphs. The conjecture in the strongest possible sense. The chapter also shows that it holds right at the time the random graph process creates a connected graph. It considers the acquaintance time of random r-uniform hypergraphs, and also considers the acquaintance time of random geometric graphs. The chapter then considers the acquaintance time for random percolated geometric graphs.
