On Wiener index of graph complements

Document Type: Research Paper

Authors

1 Anna University

2 University of Kragujevac Kragujevac, Serbia

Abstract

‎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‎.

Keywords

Main Subjects

References

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
Transactions on Combinatorics

Volume 3, Issue 2
June 2014
Pages 11-15

Files

Share

How to cite

Statistics