Exact geodetic number and its upper bound for random graphs

The problem has chosen for this thesis work is coming from graph theory. It is a computationally difficult problem called geodetic number. The work was divided into two parts. In the first part we wanted to find the exact geodetic number for random graphs by using Binary Linear Programming. The model taken from the literature was tested on a large set of random graphs. These tests serve as baselines for the second part of the work. In phase two the task was to find upper bounds of the geodetic number. The computational results show that the developed upper bound schemes give perfect results with very good execution time compared to the exact results and execution time of the original linear programming model. Also, in the second part of the project we investigated the relationship between centrality values and geodetic nodes. Based on empirical observations we derived some basic rules which could be able to identify the geodetic nodes using their centrality values. Due to the high variety of the ranking of the nodes in our test graphs it was non-trivial to propose a general rule covering all the possibilities. Nevertheless, the scheme itself is worth further consideration which we plan to do in our forthcoming scientific work.