Transit in graphs

Abstract

In the thesis titled ’Transit in Graphs’, a graph invariant called ”Transit Index” is introduced. Analysis of the transit index in alkanes showed that the correlation between MON, a physical property of alkanes and this index is significant. The transit of a vertex in a graph is the sum of the length of all the shortest paths passing through it. The sum of the transit of every vertex in the graph is termed as transit index of a graph.Some bounds for the transit of a vertex are attained. Given the adjacency matrix of a graph, an effective method of computing the transit index is devised. The relationship between the transit index of a tree and its wiener index is established. An expression for the transit index of a path is derived. It is established that the path has the maximum transit index among trees of the same order. Also, the transit index is computed for various graph classes.An investigation on how individual graph knowledge helps in the computation of transit of vertices/ transit index, in graph products is carried out. Transit equivalent class, transit dominant class and transit null graph are defined. The concept of majorized shortest paths, which facilitate the computation of the transit index of a graph is defined. Transit decomposition, which utilizes the notion of majorized shortest paths in a graph is studied. Transit decomposition number is defined and they are computed for a few graphs. Transit index and transit decomposition are explored in subdivision graphs.Graph isomorphism is a phenomenon in which the same graph appears in different forms. In Chapter 6 we look at graphs displaying similar transit decom position. Such graphs are termed transit isomorphic. The occurrence of transit isomorphism between a graph and its line graph is investigated. We also identify certain graph classes that are transit isomorphic to each other.Amalgamations can reduce a graph to a simpler graph while keeping certain structures intact. Transit of vertices in the convex amalgamation of graphs is studied. The transit index being graph invariant finds application in chemical graph theory. The transit of a vertex can be treated as a centrality measure in networks. It was established that the transit index of alkanes has a strong correlation with the physical property MON (motor octane number). Transit decomposition also gives an insight into this physical property. In transportation networks, the concept of the transit of a vertex can be a functional tool.