ON RELAXED SOLTES'S PROBLEM

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

Výsledek na webu

<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

—

Jazyk výsledku

angličtina

Název v původním jazyce

ON RELAXED SOLTES'S PROBLEM

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

ON RELAXED SOLTES'S PROBLEM

Popis výsledku anglicky

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.

Druh

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

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

0231-6986

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