Naslov
Graphs preserving total distance upon vertex removal

Autori
Knor, Martin ; Majstorović, Snježana ; Škrekovski, Riste

Izvornik
Electronic notes in discrete mathematics (1571-0653) 68 (2018); 107-112

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
total distance ; transmission ; unicyclic graph ; pendant vertex ; induced subgraph

Sažetak
The total distance or Wiener index of a connected graph G is defined as the sum of distances between all pairs of vertices in G. In 1991, Šoltés posed the problem of finding all graphs G such that the equality holds for all their vertices v. Up to now, the only known graph with this property is the cycle C11. Our main object of study is a relaxed version of this problem: Find graphs for which total distance does not change when a particular vertex is removed. We show that there are infinitely many graphs that satisfy this property. This gives hope that Šoltes's problem may have also some solutions distinct from C11.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA