# Broadcasting in Stars of Cliques and Path-Connected Cliques +
## 5 Broadcasting in Path-Connected Cliques
### Broadcasting in Path-Connected Cliques from Path Vertices  
Vertices in the path-connected cliques graph can be categorized as _path vertices_ and _clique vertices_. Within path vertices, vertices \(u_{1}\) and \(u_{k}\) are collectively referred to as _path-end vertices_, while all other path vertices are called _internal path vertices_. **Lemma 10**: _Let \(G_{k}=(P,C_{1},C_{2},\ldots,C_{k})\) be a graph of path-connected cliques. Let \(H_{i}=(P_{i},C_{i},C_{i+1},\ldots,C_{k})\) be a subgraph of \(G_{k}\) where \(P_{i}\) consists of vertices \(u_{i},u_{i+1},\ldots,u_{k}\) for all \(1\leq i\leq k\). If vertex \(u_{1}\) is the originator, then \(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\)._  
In any broadcast scheme for originator \(u_{i}\) in subgraph \(H_{i}\), \(u_{i}\) must inform \(u_{i+1}\) at some time unit \(a_{i}\) to ensure broadcasting is completed in clique \(C_{i}\) as well as subgraph \(H_{i+1}\). In an optimal scheme, \(u_{i}\) waits until the very last moment to inform \(u_{i+1}\) in such a way that the broadcasting process in \(H_{i}\) completes either simultaneously with or before the broadcasting process in \(C_{i}\). Additionally, \(u_{i}\) tries to minimize the number of vertices in \(C_{i}\) that it does not inform because it is busy informing \(u_{i+1}\). Figure 2: General Structure of the Path-Connected Cliques graph. Consider the subgraph \(H_{k-2}\). We know that vertex \(u_{k-2}\) informs \(u_{k-1}\) at time unit \(a_{k-2}\). From Lemma 9, we also know that \(b(u_{k-1},H_{k-1})=\max\{\lceil\log(l_{k-1}+2^{t_{k-1}-a_{k-1}})\rceil,a_{k-1}+ \lceil\log l_{k}\rceil\}\). Once \(u_{k-1}\) is informed, broadcasting in \(H_{k-1}\) finishes in \(b(u_{k-1},H_{k-1})\) time units. As seen in Lemma 9, all vertices in \(C_{k-2}\) will be informed by time unit \(\lceil\log(l_{k-2}+2^{t_{k-2}-a_{k-2}})\rceil\). Hence, the broadcast time of \(H_{k-2}\) from originator \(u_{k-2}\) is given by \(b(u_{k-2},H_{k-2})=\max\{\lceil\log(l_{i}+2^{t_{i}-a_{i}})\rceil,a_{i}+b(u_{i+1 },H_{i+1})\}\) and \(b(u_{k},H_{k})=\lceil\log l_{k}\rceil\). In general, for all \(1\leq i\leq k\) the broadcast time of any subgraph \(H_{i}\) from originator \(u_{i}\) is given by \(b(u_{i},H_{i})=\max\{\lceil\log(l_{i}+2^{t_{i}-a_{i}})\rceil,a_{i}+b(u_{i+1 },H_{i+1})\}\) and \(b(u_{k},H_{k})=\lceil\log l_{k}\rceil\). A similar result can be obtained when the originator is vertex \(u_{k}\). **Remark 3**. : _From Lemma 10 we know that \(b(u_{1},H_{1})=\max\{\lceil\log(l_{1}+2^{t_{1}-a_{1}})\rceil,a_{1}+b(u_{2},H_{ 2})\}\). Also, it is evident that \(b(u_{1},G_{k})=b(u_{1},H_{1})\). Hence, \(b(u_{1},G_{k})=\max\{\lceil\log(l_{1}+2^{1-a_{1}})\rceil,a_{1}+b(u_{2},H_{2} )\}\) where \(b(u_{k},H_{k})=\lceil\log l_{k}\rceil\). Alternatively, \(b(u_{1},G_{k})\) is also given by_  
\[b(u_{1},G_{k})= \begin{cases}1+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^{t_{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^{t_{1}}-l_{1}<2^{b(u_{2},H_{2})}\end{cases} \]  
**Lemma 11**. : _Let \(G_{k}=(P,C_{1},C_{2},\ldots,C_{k})\) be a graph of path-connected cliques. Then, for all \(2\leq i\leq k-1\), \(\max\{b(u_{1},G_{k}),b(u_{k},G_{k})\}\geq b(u_{i},G_{k})\)_  
Proof. : For an originator vertex \(u_{i}\), let \(H_{l}\) be the subgraph of \(G_{k}\) with all cliques to the left of \(C_{i}\). Then, \(H_{l}=(P_{l},C_{i-1},C_{i-2},\ldots,C_{1})\), where \(P_{l}\) contains vertices \(u_{i-1},u_{i-2},\ldots,u_{1}\). Similarly, let \(H_{r}\) be the subgraph with all cliques to the right of \(C_{i}\). Then, \(H_{r}=(P_{r},C_{i+1},C_{i+2},\ldots,C_{k})\), where \(P_{r}\) contains vertices \(u_{i+1},u_{i+2},\ldots,u_{k}\). Without loss of generality, assume \(b(u_{i-1},H_{l})\geq b(u_{i+1},H_{r})\). Consider the following broadcast scheme:  
1.