×

Density results for Graovac-Pisanski’s distance number. (English) Zbl 1479.05057

Summary: 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.

MSC:

05C09 Graphical indices (Wiener index, Zagreb index, Randić index, etc.)
05C12 Distance in graphs
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C35 Extremal problems in graph theory
05C92 Chemical graph theory
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. R. Ashrafi and H. Shabani, The modified Wiener index of some graph operations,Ars Math. Contemp.11(2016), 277-284, doi:10.26493/1855-3974.801.968. · Zbl 1360.05046
[2] D. Bonchev and N. Trinajsti´c, Information theory, distance matrix, and molecular branching,J. Chem. Phys.67(1977), 4517-4533, doi:10.1063/1.434593.
[3] R. Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe,Compositio Math.6 (1939), 239-250,http://www.numdam.org/item?id=CM_1939__6__239_0. · JFM 64.0596.02
[4] A. Graovac and T. Pisanski, On the Wiener index of a graph,J. Math. Chem.8(1991), 53-62, doi:10.1007/bf01166923, mathematical chemistry and computation (Dubrovnik, 1990).
[5] I. Gutman and T. K¨ortv´elyesi, Wiener indices and molecular surfaces,Z. Naturforsch.50 (1995), 669-671, doi:10.1515/zna-1995-0707.
[6] I. Gutman and O. E. Polansky, Wiener numbers of polyacenes and related benzenoid molecules, Match20(1986), 115-123,https://match.pmf.kg.ac.rs/content20.htm. · Zbl 0601.05046
[7] M. A. Iranmanesh and H. Shabani, The symmetry-moderated Wiener index of truncation graph, Thorn graph and caterpillars,Discrete Appl. Math.269(2019), 41-51, doi:10.1016/j.dam.2018. 05.040. · Zbl 1426.05028
[8] M. Knor, J. Komorn´ık, R. ˇSkrekovski and A. Tepeh, Unicyclic graphs with the maximal value of Graovac-Pisanski index,Ars Math. Contemp.17(2019), 455-466, doi:10.26493/1855-3974. 1925.57a. · Zbl 1439.05056
[9] M. Knor, R. ˇSkrekovski and A. Tepeh, Chemical graphs with the minimum value of Wiener index,Match Commun. Math. Comput. Chem.81(2019), 119-132,https://match.pmf. kg.ac.rs/content81n1.htm. · Zbl 1471.92444
[10] M. Knor, R. ˇSkrekovski and A. Tepeh, Mathematical aspects of Wiener index,Ars Math. Contemp.11(2016), 327-352, doi:10.26493/1855-3974.795.ebf. · Zbl 1355.05099
[11] B. Mohar and T. Pisanski, How to compute the Wiener index of a graph,J. Math. Chem.2 (1988), 267-277, doi:10.1007/bf01167206.
[12] R. Pinal, Effect of molecular symmetry on melting temperature and solubility,Org. Biomol. Chem.2(2004), 2692-2699, doi:10.1039/b407105k.
[13] H. Wiener, Correlation of heats of isomerization, and differences in heats of vaporization of isomers, among the paraffin hydrocarbons,J. Am. Chem. Soc.69(1947), 2636-2638, doi: 10.1021/ja01203a022.
[14] H. Wiener, Structural determination of paraffin boiling points,J. Am. Chem. Soc.69(1947), 17-20, doi:doi.org/10.1021/ja01193a005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.