# Broadcasting in Stars of Cliques and Path-Connected Cliques +
## 5 Broadcasting in Path-Connected Cliques
### Broadcasting in Path-Connected Cliques from Clique Vertices  
All non-path vertices within some clique \(C_{i}\) will have the same broadcast time; in any optimal scheme, a non-path originator \(v_{i}\) will inform the nearest path vertex \(u_{i}\) at time unit 1 since \(u_{i}\) can contribute to broadcasting within clique \(C_{i}\) as well as the path. Since all non-path vertices within some clique \(C_{i}\) are all connected to the same path vertex, they will all have the same broadcast time. Thus, to determine the broadcast time from an arbitrary originator, we must first identify the worst originator among all clique vertices.  
Lemma 12: _Let \(G_{k}=(P,C_{1},C_{2},\ldots,C_{k})\) be a graph of path-connected cliques. Then, for some vertex \(v_{1}\in C_{1}\), \(b(v_{1},G_{k})=\max\{\lceil\log(l_{1}+2^{l_{1}-a_{1}})\rceil,1+a_{1}+b(u_{2},H _{2})\}\) where \(b(u_{i},H_{i})=\max\{\lceil\log(l_{i}+2^{l_{i}-a_{i}})\rceil,a_{i}+b(u_{i+1},H _{i+1})\}\) and \(b(u_{k},H_{k})=\lceil\log l_{k}\rceil\)._  
Proof.: Without the loss of generality, assuming that \(u_{1}\) is the originator, \(v_{1}\) is the first vertex to be informed in \(C_{1}\). Then, if \(a_{1}\
eq 1\), originator \(u_{1}\) informs \(v_{1}\) at time unit 1. In an optimal broadcast scheme, originator \(v_{1}\) informs \(u_{1}\) at time unit 1 since \(u_{1}\) is a vertex in \(C_{1}\) and a path vertex. For either originator, the only informed vertices in \(G_{k}\) after one time unit are \(v_{1}\) and \(u_{1}\). Hence, the remaining steps of broadcasting and the broadcast time are the same for both originators when \(a_{1}\
eq 1\).  
When \(a_{1}=1\), by definition, originator \(u_{1}\) informs \(u_{2}\) at time unit 1. However, this is not possible when \(v_{1}\) is the originator as \(v_{1}\) informs \(u_{1}\) at time unit 1, delaying broadcasting in \(H_{2}\) by one time unit. Overall, broadcasting in \(H_{2}\) completes at time unit \(2+b(u_{2},H_{2})\). Since \(a_{1}=1\), we know that \(b(u_{2},H_{2})\geq b(u_{1},C_{1})\). Broadcasting in \(C_{1}\) finishes before \(H_{2}\) due to the added delay in \(H_{2}\). Thus, \(b(v_{1},G_{k})=2+b(u_{2},H_{2})\) when \(a_{1}=1\).  
In general, the broadcast time of \(G_{k}\) from originator \(v_{1}\) is given by \(b(v_{1},G_{k})=\max\{\lceil\log(l_{1}+2^{l_{1}-a_{1}})\rceil,1+a_{1}+b(u_{2},H_{2})\}\), where \(b(u_{i},H_{i})=\max\{\lceil\log(l_{i}+2^{l_{i}-a_{i}})\rceil,a_{i}+b(u_{i+1}, H_{i+1})\}\) and \(b(u_{k},H_{k})=\lceil\log l_{k}\rceil\). Alternatively, \(b(v_{1},G_{k})\) is also given by  
\[b(v_{1},G_{k})=\begin{cases}2+b(u_{2},H_{2})&\text{if }b(u_{2},H_{2})\geq \lceil\log l_{1}\rceil\\ \lceil\log l_{1}\rceil&\text{if }b(u_{2},H_{2})<\lceil\log l_{1}\rceil\text{ and }2^{l_{1}}-l_{1}\geq 2^{b(u_{2},H_{2})}\\ \lceil\log l_{1}\rceil+1&\text{if }b(u_{2},H_{2})<\lceil\log l_{1}\rceil\text{ and }2^{l_{1}}-l_{1}<2^{b(u_{2},H_{2})}\end{cases}\]  
A similar result can be shown for broadcasting in \(G_{k}\) from vertex \(v_{k}\in C_{k}\).  
Remark 4: _From Lemma 12, we can see that \(b(v_{1},G_{k})\geq b(u_{1},G_{k})\) by at most 1. Similarly, \(b(v_{k},G_{k})\geq b(u_{k},G_{k})\). Thus, \(b(G_{k})=\max\{b(v_{1},G_{k}),b(v_{k},G_{k})\}\)._