# Graph Theory Approach to the Vulnerability of Transportation Networks
## 2 Materials and Methods
### Selected Domination Concepts in Graph Theory  
The domination theory in graphs has various applications, where the analysis of the communications network is one of most discussed in the literature [27; 28; 29; 30; 31; 32; 33]. Hence, the idea to apply the selected methods or parameters to the transportation network research field. One of these parametersis the dominating set and domination number. According to results given in [27] a set \(D\subseteq V(G)\) is a dominating set of graph \(G\), if for any \(v\in V(G)\) either \(v\in D\) or \(N_{G}(v)\cap D=\varnothing\). While the minimum cardinality of a dominating set of graphs \(G\) is called a domination number of \(G\) and denoted as \(\gamma(G)\). The above definitions refer to the general terms of undirected graphs. There are concepts related to weight functions, which allows one to define the vertex-weighted and edge-weighted graphs [23; 27; 30]. Generally, a vertex-weighted graph \((G,w_{v})\) is defined as a graph \(G\) together with a positive weight-function on its vertex set \(w_{v}:\ V(G)\to\mathrm{R}>0\). Similarly, an edge-weighted graph \((G,w_{e})\) is defined as a graph \(G\) together with a positive weight-function on its edge set \(w_{e}:\ E(G)\to\mathrm{R}>0\). These definitions are needed to define different types of weighted domination numbers in an undirected graph. Two of them are as follows [30]:  
* The weighted domination number \(\gamma_{w}\) of \((G,w_{v})\) is the minimum weight \(w(D)=\sum_{v\in D}w(v)\) of a set \(D\subseteq V(G)\) such that every vertex \(v\in V\) is in \(D\) or has a neighbor in \(D\);
* The weighted independent domination number of \(\gamma_{I_{w}}\) of \((G,w_{v})\) is the minimum weight \(w(D_{I})=\sum_{v\in D_{I}}w(v)\) of a set \(D_{I}\subseteq V(G)\) such that no two vertices of \(D_{I}\) are connected by any edge of \((G,w)\). Similarly, it can be done for directed graphs. Taking into account the complexity of the minimum dominating set, we should state, that in general it is an NP-hard problem. Efficient approximation algorithms work out under the assumption that any dominating set problem can be formulated as a set covering problem. Thus, the greedy algorithm for finding dominating set is an analog of one that has been presented in [30; 34]. The Algorithm 1 is formulated as follows [30; 34]. ```
1:Input\(G=(V,E)\);
2:Output Dominating set of graph \(G\);
3: Let \(V=1,...,m\) and \(D=\phi\) define;
4: Greedy adds a new node to \(D\) in each iteration, until \(D\) forms a dominating set;
5: A node \(j\), is said to be covered if \(j\in D\) or if any neighbor of \(j\) is in \(D\). A node that is not covered is said to be uncovered;
6: In each iteration, put into \(D\) the least indexed node that covers the maximum number of uncovered nodes;
7: Stop when all the nodes are covered. ```  
**Algorithm 1** Dominating-set-1. The concept of the above algorithm is based on the greedy addition of vertices with the largest number of uncovered neighbors. And the Algorithm 2 is as follows [30; 34]. ```
1:Input\(G=(V,E)\);
2:Output Dominating set of graph \(G\);
3: Let \(S:=0\); all vertices are white ;
4:while (white vertices exist) do
5: Select \(v\in\{x|w(x)=\max_{u\in V}\left\{w(u)\right\}\}\);
6:\(S:=S\cup\{v\}\); vertices in \(S\) get black color and their neighbors get the gray color;
7:endwhile. ```  
**Algorithm 2** Dominating-set-2. The above algorithm, like Algorithm 1, greedily selects white vertices and colors them in black and their neighbors in gray. In the case of the minimum connected dominating set, the greedy algorithm is also used. However, to define them some preliminaries are necessary [30; 35]. Additionally, the concepts of edge-dominating set and edge-domination numbers constitute a significant part of research on domination in graphs. According to [27; 28; 33; 34; 36], these terms are defined in the following way. The set \(X\subseteq E(G)\) is called the edge-dominating set of graph G, if every edge not in \(X\) has a neighbor in set \(X\).