Broadcast by agents in dynamic graphs

\(k \ge 2\) agents with distinct identifiers stand on distinct nodes, chosen by an adversary, of a connected undirected graph \(G = (V, E)\) with \(n\) nodes. One agent, the source agent, holds a message; the other \(k - 1\) are ignorant agents. Time runs in synchronous rounds. At the start of every round the adversary chooses the snapshot \(G_t\), any connected spanning subgraph of \(G\) (the dynamic graph is 1-interval connected); every agent then sees \(G_t\) and the position and status of every agent (global visibility), and moves along one edge of \(G_t\) or stays. An ignorant agent that is on the same node as a source agent receives the message and becomes a source agent; no message travels in any other way. Broadcast is solved when every agent holds the message. The question is, for each graph \(G\), the least \(k\) with which the agents solve broadcast against every adversary and every initial placement; time is the number of rounds.

Measures: Agents, the least number \(k\) of agents, the source agent included, with which broadcast is solved against every adversary, in the worst case over the graphs of the setting with \(n\) nodes; Time, rounds until every agent holds the message.