The Wiener index of a graph W (G) is a well studied topological index for graphs. An outstanding problem of Soltes is to find graphs G such that W (G) = W (G - v) for all vertices v epsilon V (G), with the only known example being G = C-11. We relax this problem by defining a notion of Wiener indices for signed graphs, which we denote by W-sigma(G), and under this relaxation we construct many signed graphs such that W-sigma(G) = W-sigma(G - v) for all v epsilon V (G). This ends up being related to a problem of independent interest, which asks when it is possible to 2-color the edges of a graph G such that there is a path between any two vertices of G which uses each color the same number of times. We briefly explore this latter problem, as well as its natural extension to r-colorings. (C) 2021 Elsevier Inc. All rights reserved.
NSTL
Elsevier
