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 2, and its Wiener index is equal to $\binom{n}{2}+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.
F. Buckley and F. Harary (1990). Distance in graphs. Addison-Wesley Publishing Company, Advanced Book Program, Redwood City, CA.
2
L. Chen, X. Li and M. Liu (2014). The (revised) Szeged
index and the Wiener index of a nonbipartite graph. European J. Combin.. 36, 237-246
3
P. Dankelmann and S. Mukwembi (2012). The distance concept
and distance in graphs. in: I. Gutman, B. Furtula (Eds.), Distance in molecular graphs -- theory,
Univ. Kragujevac, Kragujevac. , 3-48
4
A. A. Dobrynin, R. Entringer and I. Gutman (2001). Wiener index of trees: theory and applications. Acta Appl. Math.. 66, 211-249
5
A. A. Dobrynin, I. Gutman, S. Klavzar and
P. Zigert (2002). Wiener index of hexagonal systems. Acta Appl. Math.. 72, 247-294
6
R. C. Entringer (1997). Distance in graphs: Trees. J. Combin. Math. Combin. Comput.. 24, 65-84
7
R. C. Entringer, D. E. Jackson and D. A. Snyder (1976). Distance in graphs. Czechoslovak Math. J.. 26, 283-296
8
I. Gutman, R. Cruz and J. Rada (2014). Wiener index of
Eulerian graphs. Discrete Appl. Math.. 162, 247-250
9
I. Gutman and L. Soltes (1991). The range of the Wiener
index and its mean isomer degeneracy. Z. Naturforsch.. 46a, 865-868
10
I. Gutman, Y. N. Yeh, S. L. Lee and Y. L. Luo (1993). Some recent results in the theory of the Wiener number. Indian J. Chem.. 32A, 651-661
11
S. Klavzar and M. J. Nadjafi--Arani (2014). Wiener
index in weighted graphs via unification of
Theta^*-classes. European J. Combin.. 36, 71-76
12
M. Knor and R. Skrekovski (2014). Wiener index of
generalized 4-stars and of their quadratic line graphs. Australas. J. Comb.. 58, 119-126
13
S. Nikolic, N. Trinajstic and Z. Mihalic (1995). The Wiener index: Development and applications. Croat. Chem. Acta. 68, 105-129
14
K. Xu, M. Liu, K. C. Das, I. Gutman and B. Furtula (2014). A survey on graphs extremal with respect to
distance--based topological indices. MATCH Commun.
Math. Comput. Chem.. 71, 461-508
Top