Wiener index and graphs, almost half of whose vertices satisfy olt?s property

被引：4

作者：

Akhmejanova, Margarita ^{[1
]}

Olmezov, Konstantin ^{[1
]}

Volostnov, Aleksei ^{[1
]}

Vorobyev, Ilya ^{[2
]}

Vorob'ev, Konstantin ^{[3
]}

Yarovikov, Yury ^{[1
]}

机构：

[1] Moscow Inst Phys & Technol, Dolgoprudnyi, Russia

[2] Skolkovo Insitute Sci & Technol, Moscow, Russia

[3] Sobolev Inst Math, Novosibirsk, Russia

来源：

DISCRETE APPLIED MATHEMATICS | 2023年 / 325卷

关键词：

Wiener index; Transmission; olt?s problem; Vertex removing;

D O I：

10.1016/j.dam.2022.09.021

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The Wiener index W(G) of a connected graph G is a sum of distances between all pairs of vertices of G. In 1991, oltes formulated the problem of finding all graphs G such that for every vertex v the equality W(G) = W(G - v) holds. The cycle C11 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 12. (c) 2022 Elsevier B.V. All rights reserved.

引用

页码：37 / 42

页数：6

共 9 条

[1] On regular graphs with Šoltés vertices
Basic, Nino
Knor, Martin
Skrekovski, Riste
ARS MATHEMATICA CONTEMPORANEA, 2025, 25 (02)
[2] On graphs whose Wiener complexity equals their order and on Wiener index of asymmetric graphs
Alizadeh, Yaser
Klavzar, Sandi
APPLIED MATHEMATICS AND COMPUTATION, 2018, 328 : 113 - 118
[3] Some results on the Wiener index related to the Šoltés problem of graphs
Dobrynin, Andrey A.
Vorob'ev, Konstantin V.
DISCRETE APPLIED MATHEMATICS, 2024, 344 : 154 - 160
[4] The Wiener index of unicyclic graphs given number of pendant vertices or cut vertices
Shang-wang Tan
Qi-long Wang
Yan Lin
Journal of Applied Mathematics and Computing, 2017, 55 : 1 - 24
[5] The Wiener index of unicyclic graphs given number of pendant vertices or cut vertices
Tan, Shang-wang
Wang, Qi-long
Lin, Yan
JOURNAL OF APPLIED MATHEMATICS AND COMPUTING, 2017, 55 (1-2) : 1 - 24
[6] Wiener Index of Graphs with Fixed Number of Pendant or Cut-Vertices
Pandey, Dinesh
Patra, Kamal Lochan
CZECHOSLOVAK MATHEMATICAL JOURNAL, 2022, 72 (02) : 411 - 431
[7] Wiener index of unicycle graphs with given number of even degree vertices
Luo, Peter
Zhang, Cun-Quan
Zhang, Xiao-Dong
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2020, 12 (04)
[8] Graphs whose Wiener index does not change when a specific vertex is removed
Knor, Martin
Majstorovic, Snjezana
Skrekovski, Riste
DISCRETE APPLIED MATHEMATICS, 2018, 238 : 126 - 132
[9] Wiener index of graphs with fixed number of pendant or cut-vertices
Dinesh Pandey
Kamal Lochan Patra
Czechoslovak Mathematical Journal, 2022, 72 : 411 - 431

← 1 →