The Wiener Index of Signed Graphs

DOI10.1016/J.AMC.2021.126755arXiv2106.11869MaRDI QIDQ6370971FDOQ6370971

Authors: Sam Spiro 

Publication date: 22 June 2021

Abstract: The Wiener index of a graph $W(G)$ is a well studied topological index for graphs. An outstanding problem of v{S}olt{'e}s is to find graphs $G$ such that $W(G)=W(G-v)$ for all vertices $vinV(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_{s}igma(G)$, and under this relaxation we construct many signed graphs such that $W_{s}igma(G)=W_{s}igma(G-v)$ for all $vinV(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.

Mathematics Subject Classification ID

Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Distance in graphs (05C12) Signed and weighted graphs (05C22) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10)

This page was built for publication: The Wiener Index of Signed Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6370971)