ON RELAXED SOLTES'S PROBLEM

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F60461373%3A22340%2F19%3A43918519" target="_blank" >RIV/60461373:22340/19:43918519 - isvavai.cz</a>
Result on the web
<a href="http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1173/683" target="_blank" >http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1173/683</a>
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
ON RELAXED SOLTES'S PROBLEM
Original language description
The Wiener index is a graph parameter originating from chemical graph theory. It is defined as the sum of the lengths of the shortest paths between all pairs of vertices in given graph. In 1991, Soltes posed the following problem regarding Wiener index. Find all graphs such that its Wiener index is preserved upon removal of any vertex. The problem is far from being solved and to this day, only one such graph is known - the cycle graph on 11 vertices. In this paper we solve a relaxed version of the problem, proposed by Knor, Majstorovic and Skrekovski. The problem is to find for a given k (infinitely many) graphs such that they have exactly k vertices such that if we remove any one of them, the Wiener index stays the same. We call such vertices good vertices and we show that there are infinitely many cactus graphs with exactly k cycles of length at least 7 that contain exactly 2k good vertices and infinitely many cactus graphs with exactly k cycles of length c is an element of {5, 6} that contain exactly k good vertices. On the other hand, we prove that G has no good vertex if the length of the longest cycle in G is at most 4.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10102 - Applied mathematics

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)