A tight upper bound on acquaintance time of graphs

DOI10.1007/S00373-016-1700-4MaRDI QIDQ343701zbMATH OpenOpenAlexFDO

Authors Omer Angel, Igor Shinkar

Publication date 29 November 2016

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• A note on the acquaintance time of random graphs
• A survey of gossiping and broadcasting in communication networks
• Acquaintance time of a graph
• Acquaintance time of random graphs near connectivity threshold
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Routing Permutations on Graphs via Matchings
• Short Random Walks on Graphs
• The acquaintance time of (percolated) random geometric graphs

Cited in

(5)

• Acquaintance time of a graph
• 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

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)