# Broadcasting in Stars of Cliques and Path-Connected Cliques +
## 1 Introduction  
Rapid advancements in technology, particularly the Internet and the proliferation of parallel and distributed computing, have revolutionized global communication by enabling seamless and instantaneous data exchange over vast distances. As networks become increasingly complex, the need for efficient, secure, and scalable communication protocols has grown critical, driving research into the design of optimal network architectures to meet the evolving demands of parallel and distributed systems. This paper focuses on the field of broadcasting, which was originally introduced as a variant of the gossiping problem [1]. Broadcasting involves disseminating a message throughout a network, where informed nodes communicate the message to their uninformed neighbors through calls that occur within discrete time units. The problem is typically studied in the context of connected networks, with messages transmitted along the communication lines of the network. The process begins with a single informed node, referred to as the originator, which initiates the dissemination by informing other nodes. The broadcasting concludes when all nodes in the network have received the message. During each time unit, newly informed nodes participate in the broadcasting process by informing their uninformed neighbors. The broadcasting process operates under the following constraints: (1) Time is divided into discrete units. (2) Within each time unit, a node can participate in at most one call. (3) Each call has a fixed duration of one time unit and occurs between two neighboring nodes. (4) Multiple calls can occur simultaneously during a single time unit, provided they involve distinct pairs of neighboring nodes. A connected undirected graph \(G=(V,E)\) is used to depict the network, where \(V\) represents the set of nodes (vertices) and \(E\) represents the communication lines (edges) connecting the nodes of the network. The originator vertex is typically labelled as \(u\). The minimum time required to complete broadcasting in \(G\) from originator \(u\) is referred to as the broadcast time from originator \(u\) and is depicted by \(b(u,G)\). Assuming each informed vertex informs one of its uninformed neighbours during a given time unit, the number of informed vertices can, at most, double in each step. This observation establishes the following lower bound on the broadcast time from a given originator vertex \(u\): \(b(u,G)\geq\lceil\log n\rceil\) where \(n=|V|\). Note that all logarithms referenced in this paper are base 2. During each time unit, at least one new vertex receives the message. This observation supports the following upper bound on the broadcast time: \(b(u,G)\leq n-1\). The broadcast time of a graph is defined as the maximum broadcast time across all vertices in the graph: \(b(G)=\max\limits_{u\in V}\{b(u,G)\}\). Note that another lower bound on \(b(G)\) is the diameter of the graph, defined as the length of the shortest path between the most distanced nodes. The set of calls used to disseminate the message from a given originator vertex \(u\) to all other vertices of the graph is referred to as the _broadcast scheme_ for vertex \(u\). The broadcast scheme corresponds to the _broadcast tree_, which is a spanning tree rooted at the originator. Note that the above upper and two lower bounds are tight for some specific graphs, while this is not the case in general. For example, in the binary hypercube, both lower bounds are tight. For the star graph, which has diameter 2, the upper bound is tight but both lower bounds are much less so. Computing \(b(u,G)\) and \(b(G)\) for arbitrary graphs, given arbitrary originators, is an NP-complete problem [2]. This complexity persists even within restricted graph families, including bounded degree graphs [3] and 3-regular planar graphs [4; 5]. Approximating the broadcast time problem within a factor of \(\frac{\sqrt{2}}{56}-\epsilon\) has been proven to be NP-Hard [6].