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

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

Izvornik
Discrete applied mathematics (0166-218X) 238 (2018); 126-132

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

Ključne riječi
Wiener index, transmission, unicyclic graph, pendant vertex, induced subgraph

Sažetak
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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA