Wiener Index of Chain Graphs

A bipartite graph is called a chain graph if the neighborhoods of the vertices in each partite set form a chain with respect to set inclusion. Chain graphs are discovered and re-discovered by various researchers in various contexts. Also, they were named differently according to the applications in which they arise. In the field of Spectral Graph Theory, chain graphs play a remarkable role. They are characterized as graphs with the largest spectral radius among all the connected bipartite graphs with prescribed number of edges and vertices. Even though chain graphs are significant in the field of Spectral Graph Theory, the area of graph parameters remains untouched. Wiener index is one of the oldest and most studied topological indices, both from theoretical point of view and applications. The Wiener index of a graph is defined as the sum of distances between every pair of vertices in it. In this article, we give bounds for Wiener index and hence for average distance of chain graphs. We also present a quadratic time algorithm that returns a realising chain graph G (if exists) whose Wiener index is the given integer w. The algorithm presented in this article contributes to the existing knowledge in the theory of inverse Wiener index problem. We conclude this article by exploring some more graph parameters called edge Wiener index, hyper Wiener index and Zagreb indices of chain graphs. Index Terms—Bipartite graphs, Bi-star graph, Edge Wiener index, Average distance, Zagreb index, Hyper Wiener index.