On relaxed Šoltés's problem

Kód výsledku v 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>

Výsledek na webu

<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

—

Jazyk výsledku

angličtina

Název v původním jazyce

On relaxed Šoltés's problem

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On relaxed Šoltés's problem

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2019

Kód důvěrnosti údajů

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

Název periodika

Acta Mathematica Universitatis Comenianae

ISSN

0862-9544

e-ISSN

—

Svazek periodika

88

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

SK - Slovenská republika

Počet stran výsledku

6

Strana od-do

475-480

Kód UT WoS článku

000484349000019

EID výsledku v databázi Scopus

2-s2.0-85078507997