A tight upper bound on acquaintance time of graphs

DOI10.1007/S00373-016-1700-4zbMATH Open1351.05211arXiv1307.6029OpenAlexW1494111593MaRDI QIDQ343701FDOQ343701

Authors: Omer Angel, Igor Shinkar 

Publication date: 29 November 2016

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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)leq20Deltan$. Combining this with the bound $AC(G)leqO(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 $ceiln/2$ and $floorn/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.

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

Recommendations

• A note on the acquaintance time of random graphs
• Acquaintance time of a graph
• Acquaintance time of random graphs near connectivity threshold
• The acquaintance time of (percolated) random geometric graphs
• On the time to identify the nodes in a random graph
• On constant time approximation of parameters of bounded degree graphs
• Approximation algorithms in graphs with known broadcast time of the base graph
• An upper bound on the cover time for powers of graphs
• scientific article; zbMATH DE number 219254
• On a certain complexity estimate in graph theory

zbMATH Keywords

acquaintance time of graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• A survey of gossiping and broadcasting in communication networks
• Title not available (Why is that?)
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• The acquaintance time of (percolated) random geometric graphs
• Acquaintance time of random graphs near connectivity threshold
• Acquaintance time of a graph
• A note on the acquaintance time of random graphs
• Routing Permutations on Graphs via Matchings
• Short Random Walks on Graphs

Cited In (5)

• The acquaintance time of (percolated) random geometric graphs
• Acquaintance time of random graphs near connectivity threshold
• Collision-free network exploration
• A note on the acquaintance time of random graphs
• Acquaintance time of a graph

This page was built for publication: A tight upper bound on acquaintance time of graphs

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