{
  "id": "1307.6029",
  "version": "v1",
  "published": "2013-07-23T11:47:48.000Z",
  "updated": "2013-07-23T11:47:48.000Z",
  "title": "A Tight Upper Bound on Acquaintance Time of Graphs",
  "authors": [
    "Omer Angel",
    "Igor Shinkar"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "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 $G$ with $n$ 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 $G$ with $n$ vertices and maximal degree $\\Delta$ it holds that $\\AC(G) \\leq 20 \\Delta n$. Combining this with the bound $\\AC(G) \\leq O(n^2/\\Delta)$ from \\cite{BST} gives the foregoing uniform upper bound of all $n$-vertex graphs. We also prove that for the $n$-vertex path $P_n$ it holds that $\\AC(P_n)=n-2$. In addition we show that the barbell graph $B_n$ 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 $\\Omega(n^2)$ edges to $P_n$ without changing the $\\AC$ value of the graph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-07-23T11:47:48.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "tight upper bound",
      "acquaintance time",
      "foregoing uniform upper bound",
      "maximal degree",
      "vertex graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1307.6029A"
    }
  }
}