Some results on the Wiener index related to the Soltes problem of graphs

Some results on the Wiener index related to the Soltes problem of graphs Full article

Journal

Discrete Applied Mathematics
ISSN: 0166-218X

Output data

Year: 2024, Volume: 344, Pages: 154-160 Pages count : 7 DOI: 10.1016/j.dam.2023.11.041

Authors

Dobrynin Andrey A. ¹ , Vorob’ev Konstantin V. ^1,2

Affiliations

1	Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090, Russia
2	Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, Sofia 1113, Bulgaria

Funding (1)

Russian Science Foundation

23-21-00459

The Wiener index, W(G), of a connected graph G is the sum of distances between its vertices. In 2021, Akhmejanova et al. posed the problem of finding graphs G with large Rm(G) = |{v ∈ V (G) |W(G) − W(G − v) = m ∈ Z}|/|V (G)| for any integer m ≥ 0. It is shown that there is a graph G with Rm(G) > 1/2 for any m ≥ 0. In particular, there is a regular graph of even degree with this property for any odd m ≥ 1. The proposed approach allows to construct new families of graphs G with R0(G) → 1/2 when the order of G increases.

Dobrynin A.A. , Vorob’ev K.V.
Some results on the Wiener index related to the Soltes problem of graphs
Discrete Applied Mathematics. 2024. V.344. P.154-160. DOI: 10.1016/j.dam.2023.11.041 WOS Scopus РИНЦ OpenAlex

Submitted:	Apr 26, 2023
Accepted:	Nov 23, 2023
Published online:	Dec 27, 2023
Published print:	Feb 15, 2024

Web of science:	WOS:001127792200001
Scopus:	2-s2.0-85178346596
Elibrary:	64925859
OpenAlex:	W4389066992

DB	Citing
OpenAlex	2
Scopus	2
Web of science	2