On Wiener index of graph complements

‎Let G be an (n,m)-graph‎. ‎We say that G has property (\ast)‎ ‎if for every pair of its adjacent vertices x and y‎, ‎there ‎exists a vertex z‎, ‎such that z is not adjacent‎ ‎to either x or y‎. ‎If the graph G has property (\ast)‎, ‎then‎ ‎its complement \overline G is connected‎, ‎has diameter ۲‎, ‎and its‎ ‎Wiener index is equal to \binom{n}{۲}+m‎, ‎i.e.‎, ‎the Wiener index‎ ‎is insensitive of any other structural details of the graph G‎. ‎We characterize numerous classes of graphs possessing property (\ast)‎, ‎among which are trees‎, ‎regular‎, ‎and unicyclic graphs‎.

Keywords:

distance (in graphs) , Wiener index , complement (of graph)