Broadcasting on Paths and Cycles

DOI10.1016/J.DISC.2022.112883MaRDI QIDQ6354552arXivFDO

Authors Reaz Huq, Paweł Prałat

Publication date 24 November 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.DISC.2022.112883

Mathematics Subject Classification ID

Paths and cycles (05C38) Random walks on graphs (05C81)

arXiv classification

math.COmath.PR

Abstract: Consider the following broadcasting process run on a connected graph $G=(V,E)$. Suppose that $kge2$ agents start on vertices selected from $V$ uniformly and independently at random. One of the agents has a message that she wants to communicate to the other agents. All agents perform independent random walks on $G$, with the message being passed when an agent that knows the message meets an agent that does not know the message. The broadcasting time $xi(G,k)$ is the time it takes to spread the message to all agents. We provide tight bounds for $xi(P_n,k)$ and $xi(C_n,k)$ that hold asymptotically almost surely for the whole range of the parameter~$k$.

This page was built for publication: Broadcasting on Paths and Cycles

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