engleski

Graphs whose Wiener index does not change when a specific vertex is removed

The Wiener index W(G) of a connected graph G is defined to be the sum of distances between all pairs of vertices in G. In 1991, Solt´es studied changes of ˇ the Wiener index caused by removing a single vertex. He posed the problem of finding all graphs G so that equality W(G) = W(G−v) holds for all their vertices v. The cycle with 11 vertices is still the only known graph with this property. In this paper we study a relaxed version of this problem and find graphs which Wiener index does not change when a particular vertex v is removed. We show that there is a unicyclic graph G on n vertices with W(G) = W(G − v) if and only if n ≥ 9. Also, there is a unicyclic graph G with a cycle of length c for which W(G) = W(G − v) if and only if c ≥ 5. Moreover, we show that every graph G is an induced subgraph of H such that W(H) = W(H − v). As our relaxed version is rich with solutions, it gives hope that Soltes’s problem may have also some solutions distinct from C11.

Wiener index, transmission, unicyclic graph, pendant vertex, induced subgraph

nije evidentirano