engleski

Graphs preserving total distance upon vertex removal

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.

total distance ; transmission ; unicyclic graph ; pendant vertex ; induced subgraph

nije evidentirano