Density results for Graovac-Pisanski’s distance number

Lowell Abrams ; Lindsey-Kay Lauderdale

Ars Mathematica Contemporanea, Tome 21 (2021) no. 2, article no. 05, 15 p.

Résumé

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. Graovac and Pisanski 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 Γ 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 Γ. 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.

Détail

DOI : 10.26493/1855-3974.2351.07b

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