A Tight Upper Bound on Acquaintance Time of Graphs
arXiv:1307.6029
Abstract
In this note we confirm a conjecture raised by Benjamini et al. \cite{BST} on the acquaintance time of graphs, proving that for all graphs with vertices it holds that $\AC(G) = O(n^{3/2})$, which is tight up to a multiplicative constant. This is done by proving that for all graphs with vertices and maximal degree it holds that $\AC(G) \leq 20 Δn$. Combining this with the bound $\AC(G) \leq O(n^2/Δ)$ from \cite{BST} gives the foregoing uniform upper bound of all -vertex graphs. We also prove that for the -vertex path it holds that $\AC(P_n)=n-2$. In addition we show that the barbell graph consisting of two cliques of sizes $\ceil{n/2}$ and $\floor{n/2}$ connected by a single edge also has $\AC(B_n) = n-2$. This shows that it is possible to add edges to without changing the $\AC$ value of the graph.