The Wiener Index of Signed Graphs

2021/06/22 by Spiro, Sam · 1 citation
#05C12 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2106.11869

Abstract

The Wiener index of a graph W(G) is a well studied topological index for graphs. An outstanding problem of Šoltés is to find graphs G such that W(G)=W(G-v) for all vertices v∈ V(G), with the only known example being G=C₁₁. We relax this problem by defining a notion of Wiener indices for signed graphs, which we denote by W_σ(G), and under this relaxation we construct many signed graphs such that W_σ(G)=W_σ(G-v) for all v∈ 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.

Cited by

• Uniform Šoltés' hypergraphs and Šoltés' weighted graphs

Related

• Wiener index and graphs, almost half of whose vertices satisfy Šoltés property
• Disproof of a conjecture on the minimum Wiener index of signed trees
• Some results on the Wiener index related to the Šoltés problem of graphs
• Wiener index of graphs with fixed number of pendant or cut vertices
• A note on topological indices and the twin classes of graphs