Wiener index and graphs, almost half of whose vertices satisfy Šoltés property. (English) Zbl 1504.05059
Summary: The Wiener index \(W ( G )\) of a connected graph \(G\) is a sum of distances between all pairs of vertices of \(G\). L. Šoltés [Math. Slovaca 41, No. 1, 11–16 (1991; Zbl 0765.05097)] formulated the problem of finding all graphs \(G\) such that for every vertex \(v\) the equality \(W ( G ) = W ( G - v )\) holds. The cycle \(C_{11}\) is the only known graph with this property. In this paper we consider the following relaxation of the original problem: find a graph with a large proportion of vertices such that removing any one of them does not change the Wiener index of a graph. As the main result, we build an infinite series of graphs with the proportion of such vertices tending to \(\frac{ 1}{ 2} \).
MSC:
| 05C09 | Graphical indices (Wiener index, Zagreb index, Randić index, etc.) |
| 05C12 | Distance in graphs |
| 92E10 | Molecular structure (graph-theoretic methods, methods of differential topology, etc.) |
| 05C92 | Chemical graph theory |
Citations:
Zbl 0765.05097References:
| [1] | Bok, J.; Jedličková, N.; Maxová, J., On relaxed šoltés’s problem, Acta Math. Univ. Comenianae, 88, 3, 475-480 (2019) |
| [2] | Dobrynin, A.; Entringer, R.; Gutman, I., Wiener index of trees: theory and applications, Acta Appl. Math., 66, 3, 211-249 (2001) · Zbl 0982.05044 |
| [3] | Egorov, A.; Vesnin, A., On correlation of hyperbolic volumes of fullerenes with their properties, Comput. Math. Biophys., 8, 1, 150-167 (2020) · Zbl 1472.92292 |
| [4] | Hosoya, H., Topological index, a newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bull. Chem. Soc. Jpn., 44, 9, 2332-2339 (1971) |
| [5] | Knor, M.; Majstorović, S.; Škrekovski, R., Graphs preserving Wiener index upon vertex removal, Appl. Math. Comput., 338, 25-32 (2018) · Zbl 1427.05072 |
| [6] | Knor, M.; Majstorović, S.; Škrekovski, R., Graphs whose Wiener index does not change when a specific vertex is removed, Discrete Appl. Math., 238, 126-132 (2018) · Zbl 1380.05048 |
| [7] | Knor, M.; Škrekovski, R.; Tepeh, A., Mathematical aspects of Wiener index, Ars Math. Contemp., 11, 2, 327-352 (2016) · Zbl 1355.05099 |
| [8] | Šoltés, L., Transmission in graphs: a bound and vertex removing, Math. Slovaca, 41, 1, 11-16 (1991) · Zbl 0765.05097 |
| [9] | Wiener, H., Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69, 1, 17-20 (1947) |
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.
