## 2 Materials and Methods
### Graph Theory  
The notations used to describe the proposed algorithm are presented in Table 2.  
Thus, the concept of graph theory such as dominating sets and set covers have been employed and the terminologies are given as follows:  
**Definition 1** (Dominating Set): _Let \(G=(V,\,E)\) be a graph. A vertex \(v\in V\) is said to be dominated by another vertex \(u\in V\), if \((u,\,v)\in E\). A set \(D\subseteq V\) is called a dominating set of \(G\) if for every vertex \(v\in V\) is either \(v\) is in \(D\), or it is dominated by some vertex \(u\in D\)._ \begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Description** \\ \hline \(Id\) & Vehicle Id \\ \(Dir\) & Direction of Movement of Vehicle \\ _Colour_ & State of Vehicle (white, black, blue, red, yellow, grey) \\ \(S\) & Speed of Vehicle \\ \(C_{id}\) & Cluster Id \\ \(N_{u}\) & Set of all Neighbour Vehicles’ Ids \\ \(CH\) & Cluster Head \\ \(GW\) & Gateway \\ \(CCH\) & Candidate Cluster Head \\ \(CG\) & Candidate Gateway \\ \(DC_{u}\) & Degree of Cohesion of Vehicle \(u\) \\ \(rm_{uv}\) & Relative Mobility between Vehicle \(u\) and Vehicle \(v\) \\ \(d_{uv}\) & Distance between Vehicle \(u\) and Vehicle \(v\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Notation. Figure 1: Network model: simulation of highway with 4 lanes in each direction. **Definition 2** (Minimal Dominating Set): _A dominating set \(D\) is said to be a minimal dominating set if none of the proper subsets of \(D\) is also a dominating set. The number of vertices in a minimal dominating set of graph \(G\) is known as the dominance number \(\gamma(G)\)._  
**Definition 3** (Minimum Connected Dominating Set): _If the subgraph induced by dominating set \(D\) is connected, then \(D\) is said to be a connected dominating set. If no proper subset of \(D\) is a connected dominating set, then \(D\) is called a minimum connected dominating set and the number of vertices in \(D\) is known as connected dominance number, \(\gamma_{c}(G)\). Figure 2 provides a clear distinction between Minimal Dominating Set and Minimum Connected Dominating Set using an example._  
**Definition 4** (Minimum Set Cover): _Given a universe \(\mathbb{U}\) and a family \(\mathcal{F}\) of subsets of \(\mathbb{U}\), a set cover is a subfamily \(\mathcal{C}\subseteq\mathcal{F}\) of sets whose union is \(\mathbb{U}\), the set cover with minimum size is called minimum set cover._  
Consider \(\mathbb{U}=\{1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9,\ 10,\ 11,\ 12\}\), \(\mathcal{F}=\{\mathcal{S}_{1},\ \mathcal{S}_{2},\ \mathcal{S}_{3},\ \mathcal{S}_{4},\ \mathcal{S}_{5},\ \mathcal{S}_{6}\}\), where \(\mathcal{S}_{1}=\{1,\ 3,\ 5,\ 6,\ 10,\ 11\}\), \(\mathcal{S}_{2}=\{2,\ 5,\ 7,\ 9,\ 12\}\), \(\mathcal{S}_{3}=\{1,\ 3,\ 5,\ 9,\ 10,\ 12\}\), \(\mathcal{S}_{4}=\{1,\ 4,\ 7,\ 9\}\), \(\mathcal{S}_{5}=\{7,\ 8,\ 9,\ 10,\ 11,\ 12\}\), \(\mathcal{S}_{6}=\{2,\ 4,\ 6,\ 8,\ 10,\ 12\}\) and \(\mathcal{C}=\{\mathcal{S}_{1},\ \mathcal{S}_{3},\ \mathcal{S}_{4},\ \mathcal{S}_{6}\}\) is a set cover where as \(\mathcal{C}=\{\mathcal{S}_{1},\ \mathcal{S}_{2},\ \mathcal{S}_{6}\}\) is a minimum set cover. Finding the minimum connected dominating set and minimum set cover are NP-Complete problems [32,33]. Hence, a connected dominating set that is close to minimum connected dominating set and the set cover which is close to minimum set cover has been identified. The proposed algorithm aims to disseminate the information to all the vehicles approaching the region of interest with minimum rebroadcast, by clustering the vehicles into groups using the concept of dominating sets and set covers. Each vehicle calculates its degree of cohesion with its neighborhood and the vehicle with a higher degree of cohesion is selected as a cluster head and is included in the dominating set. The vehicles that receive beacons from more than one cluster head will become the candidate gateway.