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. 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 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 A. A. Dobrynin, R. Entringer and I. Gutman (2001). Wiener index of trees: theory and applications. Acta Appl. Math.. 66, 211-249 A. A. Dobrynin, I. Gutman, S. Klavzar and
P. Zigert (2002). Wiener index of hexagonal systems. Acta Appl. Math.. 72, 247-294 R. C. Entringer (1997). Distance in graphs: Trees. J. Combin. Math. Combin. Comput.. 24, 65-84 R. C. Entringer, D. E. Jackson and D. A. Snyder (1976). Distance in graphs. Czechoslovak Math. J.. 26, 283-296 I. Gutman, R. Cruz and J. Rada (2014). Wiener index of
Eulerian graphs. Discrete Appl. Math.. 162, 247-250 I. Gutman and L. Soltes (1991). The range of the Wiener
index and its mean isomer degeneracy. Z. Naturforsch.. 46a, 865-868 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 S. Klavzar and M. J. Nadjafi--Arani (2014). Wiener
index in weighted graphs via unification of
Theta^*-classes. European J. Combin.. 36, 71-76 M. Knor and R. Skrekovski (2014). Wiener index of
generalized 4-stars and of their quadratic line graphs. Australas. J. Comb.. 58, 119-126 S. Nikolic, N. Trinajstic and Z. Mihalic (1995). The Wiener index: Development and applications. Croat. Chem. Acta. 68, 105-129 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
Senbagamalar, J. , Babujee, J. B. and Gutman, I. (2014). On Wiener index of graph complements. Transactions on Combinatorics, 3(2), 11-15. doi: 10.22108/toc.2014.4577
MLA
Senbagamalar, J. , , Babujee, J. B. , and Gutman, I. . "On Wiener index of graph complements", Transactions on Combinatorics, 3, 2, 2014, 11-15. doi: 10.22108/toc.2014.4577
HARVARD
Senbagamalar, J., Babujee, J. B., Gutman, I. (2014). 'On Wiener index of graph complements', Transactions on Combinatorics, 3(2), pp. 11-15. doi: 10.22108/toc.2014.4577
CHICAGO
J. Senbagamalar , J. B. Babujee and I. Gutman, "On Wiener index of graph complements," Transactions on Combinatorics, 3 2 (2014): 11-15, doi: 10.22108/toc.2014.4577
VANCOUVER
Senbagamalar, J., Babujee, J. B., Gutman, I. On Wiener index of graph complements. Transactions on Combinatorics, 2014; 3(2): 11-15. doi: 10.22108/toc.2014.4577
)
