A study on closely connected vertices in graphs

Abstract

Graph theory is one of the thriving branches of mathematics. The smooth operation of communication networks is largely dependent on the reliability of communication infrastructure. Fault tolerance is the ability of a system to con- tinue operating as intended despite errors and the main aim is to design fault- tolerant networks by minimizing link failures. In this thesis, emphasizing on the need for fault-tolerant mechanisms for reliable communication between the nodes in a network, a new graph concept called “closely-connected vertices” is introduced and studied in a detailed manner. A pair of distinct vertices in a finite simple undirected graph is said to be closely-connected if there exists a geodesic linking them preserving the connec- tivity of the graph. The properties of closely-connected vertices are analysed for various graphs and a variation of domination called cc-domination is formulated. Further, the idea of cc-domination polynomial is developed and a topological index called vertex-connectivity index is studied. Moreover, the ideas of vertex connectivity polynomial and the stability properties of its roots are discussed. The significance of the study is analysed and the concluding chapter specifies certain recommendations of the thesis.