New upper bound on m-time-relaxed k-broadcast graphs

Broadcasting is a process in which an individual has an item of information which needs to be transmitted to all of the members in a network (which is viewed as a connected graph). k‐broadcasting is a variant of broadcasting in which each processor can transmit the message to up to k of its neighbors. Another variant of broadcasting is the concept of m‐time‐relaxed broadcasting, where we allow m additional time units, enabling one to decrease the number of edges in the communication network. The combination of m‐time‐relaxed and k‐broadcasting is studied in this article. The results shown here are an improvement on the upper bound obtained by Harutyunyan and Liestman, Discrete Math 262 (2003), 149–157, by constructing a connected graph, which admits m‐time‐relaxed k‐broadcasting for all n, n > ( k + 1 ) m + 2 , m > 1 and has fewer edges than the graph presented in Harutyunyan and Liestman, Discrete Math 262 (2003), 149–157.