On relaxed Šoltés's problem

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10403434" target="_blank" >RIV/00216208:11320/19:10403434 - isvavai.cz</a>

Result on the web

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=pk_e8RKnii" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=pk_e8RKnii</a>

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

On relaxed Šoltés's problem

Original language description

TheWiener indexis a graph parameter originating from chemical graphtheory. It is de ned as the sum of the lengths of the shortest paths between all pairsof vertices in given graph. In 1991,Soltes posed the following problem regardingWiener index. Find all graphs such that its Wiener index is preserved upon removalof any vertex. The problem is far from being solved and to this day, only one suchgraph is known { the cycle graph on 11 vertices.In this paper we solve a relaxed version of the problem, proposed by Knor,Majstorovic andSkrekovski. The problem is to nd for a givenk(in nitely many)graphs such that they have exactlykvertices such that if we remove any one ofthem, the Wiener index stays the same. We call such verticesgoodvertices and weshow that there are in nitely many cactus graphs with exactlykcycles of length atleast 7 that contain exactly 2kgood vertices and in nitely many cactus graphs withexactlykcycles of lengthc2 f5;6gthat contain exactlykgood vertices. On theother hand, we prove thatGhas no good vertex if the length of the longest cycleinGis at most 4.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2019

Confidentiality

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

Name of the periodical

Acta Mathematica Universitatis Comenianae

ISSN

0862-9544

e-ISSN

—

Volume of the periodical

88

Issue of the periodical within the volume

3

Country of publishing house

SK - SLOVAKIA

Number of pages

6

Pages from-to

475-480

UT code for WoS article

000484349000019

EID of the result in the Scopus database

2-s2.0-85078507997