Graph Indices on Grids

The Wiener index of a graph, known as the “sum of distances” of a connected graph, is the first topological index used in chemistry to sum the distances between all unordered pairs of vertices of a graph. Wiener index, or sometimes called Wiener number, of a molecular graph correlates physical and chemical characteristics of graphs, and has been studied for various kinds of graphs. In this thesis, we derived mathematical formulas to compute Wiener index and hyper-Wiener index for bodycentered cubic grid and face-centered cubic grid. In the body-centered cubic graph, the lines of unit cells of the body-centered cubic grid are used. These graphs contain center points of the unit cells and other vertices, called border vertices. Closed formulas are obtained to calculate the sum of shortest distances between pairs of border vertices, between border vertices and centers and between pairs of centers. Based on these formulas, their sum, the Wiener index and hyper-Wiener index of body-centered cubic grid with unit cells connected in a row are computed. Some relationships between formulas and integer sequences are also presented. In face-centerd cubic grid, the graphs of lines of unit cells of the face-centered cubic grid are investigated. The face-centered cubic unit cell is a cube (all sides have the same length and all faces are perpendicular to each other) with an atom at each corner of the unit cell called border points and an atom situated in the middle of each face of the unit cell called face central points. Closed formulas are obtained to calculate the sum of shortest distances between pairs of border points, between border points and centrals and between pairs of centrals. Based on these formulas, their sum, the Wiener index and hyper-Wiener index of face-centered cubic grid with unit cells connected in a row graph is computed. Keywords: Wiener index, body-centered cubic grid, face-centered cubic grid, hyper- Wiener index, shortest paths, non-traditional grids, combinatorics.