Graph Indices on Grids

Abstract

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.

ÖZ : Bir grafın mesafeler toplamı olarak bilinen Wiener indeksi, kimdaya sırasız düğüm çiftleri arasındaki mesafeler toplamını hesaplamak için kullanılan ilk topolojik indekstir. Moleküler grafın bir çok graf türü için irdelenmiş olan ve Wiener sayısı olarak da bilinen Wiener indeksi grafın fiziksel ve kimyasal özelliklerini ilişkilendirir. Bu tezde gövde-merkezli grafın birim hücrelerinin kenarlarını kullanarak gövde-merkezli ve yüzey-merkezli kübik grafın Wiener indeksi ve hiper- Wiener indeksinin hesaplanması için formül geliştirilmiştir. Bunun yanı sıra yüzeymerkezli kübik şebekelerde birim hücre dizileri biçiminde olan graflar irdelenmiştir. Yüzey-merkezli kübik birim hücre, köşeleri sınır noktaları da denilen çekirdeklerden oluşan bir küpdür. Sözkonusu graflar birim hücreleri merkez düğümlerini ve sınır düğümlerini içermektedir. Bu bağlamda önerilen formüller uygulanarak sınır düğümleri çiftleri, sinir ve merkez düğüm çiftleri ve merkez düğüm çiftleri arasındaki en kısa yollar toplamı hesaplanabilmektedir. Sözkonusu formüller ve tamsayı dizileri arasında bazı ilişkiler de bu tezde irdelenmiştir. Anahtar Kelimeler: Wiener endeksi, gövde-merkezli kübik grid, yüzey-merkezli kübik grid, hiper-Wiener endeksi, kısa yollar, Geleneksel olmayan grid, kombinatoriks.