# Graph Theory Approach to the Vulnerability of Transportation Networks
## 3 Results
### Structural Transportation Network Vulnerability  
In this subsection, the bondage-connected number is proposed as the indicator for the structural vulnerability in the transportation network. This parameter bases itself on the domination number in the graph. Thus, it is necessary to introduce some algorithms to find the minimal dominating set in a graph, which implies the domination number. The Algorithms 1 and 2 mentioned above give the dominating sets as the output. Unfortunately, very often, these sets are not minimal because all problems regarding domination sets belong to the NP class. Therefore, the following modification of Algorithms 1 and 2 is proposed to create one algorithm that finds the smallest domination set. As an input for the new Algorithm 3 is a connected, simple, non-empty graph (important assumption)```
1:Input\(G=(V,E)\). 2:Output Minimal vertex-dominating set of graph \(G\). 3: Fix \(S:=0\); all vertices are white. 4:while (white vertices exist) do
5: choose \(v\in\{x|w(x)=max_{u\in V}\{w(u)\}\}\) and it has the maximal number of white neighbor. 6:\(S:=S\cup\{v\}\); vertices in \(S\) are colored by black; their neighbors are gray. 7:endwhile. 8:return\(S\). 9:if in \(S\) there are vertices, what dominates the same vertices then
10: delete vertex from \(S\), which dominates only vertices dominated by other vertices from \(S\); return \(D=S\setminus\{v\}\)
11:else
12:\(D=S\)
13:endif
14:return\(D\)
```

**Algorithm 3** Minimal-vertex-dominating-set. Proof. : The set \(S\) is the dominating set, but it is not always the minimal one. Thus, it is necessary to check if there are vertices in this set that dominate the same vertices, and at the same time, their neighbors are dominated by other vertices from the set \(S\). If the answer is \"yes,\" then such a vertex can be removed. By repeating this operation for all vertices of \(S\) and removing those that do not dominate vertices not dominated by others, we get the smallest dominating set. The Algorithm 3 is the combination of the Algorithms 1 and 2. Steps 3-7 are similar to Algorithm 2 and steps 9-13 are based on covering concept in Algorithm 1. Unfortunately, it is still a greedy algorithm running in polynomial time. Mainly responsible for its complexity are steps: 4-7, and 9-13. Another possible solution for this problem may be the usage of the genetic algorithm. ### Weighted Structural Transportation Vulnerability

First of all, to propose the indicator for weighted structural vulnerability, the weighted bondage-connected number \(wb_{c}(G)\) of graph \(G\) has to be defined. It is described as the smallest cardinality of all edge sets, where \(\gamma_{w}(G-E)>\gamma_{w}(G)\) and graph \(G-E\) are connected. To find the value of this parameter, according to the definition, it must be known as a minimum weighted dominating set. In this way, we perceive the nodes of the network that constitute its bottlenecks. The proprietary Algorithm 4 for searching for a weighted domination number is proposed below. ```
1:Input\((G,w_{v})\) with fixed vertex weighted function;
2:Output weighted domination number \(\gamma_{w}(G)\) of graph \((G,w_{v})\);
3:for\(i=1\) to \(|V|\)do
4: find dominating set of \(G\), starting from \(v_{i}\in V\), and save it as \(D_{i}(v_{i})\);
5: find total weight \(W_{i}(v_{i})=\sum_{v_{i}\in D_{i}}w_{i}(v_{i})\) of dominating sets \(D_{i}(v_{i})\);
6:endfor;
7: find min \(\{W_{i}(v_{i}):\,v_{i}\in V,\,i=1,...,|V|\}\rightarrow\gamma_{w}(G)\);
8:return\(\gamma_{w}(G)\). ```

**Algorithm 4** Weighted-domination-number. The complexity of this algorithm is dependent on steps 7 and 8, where that sort operation is necessary to do. But this solution is at the same time a strong point of this algorithm. It is enough to add one operation to return the largest value and we get the maximal weighted dominating set of the graph \(G\). Hence, we get the next parameter for determining the transport network--the maximal capacity of the network or the largest flow in the network.