Density results for Graovac-Pisanski’s distance number

english

2021

volume 21, issue 2

chemical graph theory   distance number   Graovac-Pisanski index   graph automorphism group   Wiener index

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

The sum of distances between every pair of vertices in a graph ?$G$? is called the Wiener index of ?$G$?. This graph invariant was initially utilized to predict certain physico-chemical properties of organic compounds. However, the Wiener index of ?$G$? does not account for any of its symmetries, which are also known to effect these physico-chemical properties. A. Graovac and I. Pisanski On the Wiener index of a graph, J. Math. Chem. 8, No. 1, 53-62 (1991; doi:10.1007/BF01166923) modified the Wiener index of ?$G$? to measure the average distance each vertex is displaced under the elements of the symmetry group of ?$G$?; we call this the Graovac-Pisanski (GP) distance number of ?$G$?. In this article, we prove that the set of all GP distance numbers of graphs with isomorphic symmetry groups is dense in a half-line. Moreover, for each finite group ?$\Gamma$? and each rational number ?$q$? within this half-line, we present a construction for a graph whose GP distance number is ?$q$? and whose symmetry group is isomorphic to ?$\Gamma$?. This construction results in graphs whose vertex orbits are not connected; we also consider an analogous construction which ensures that all vertex orbits are connected.

22.11.2022