On distance in complements of graphs

Authors: Gutman Ivana, Lu Jia, Boutiche Mohamed-Amine

Keywords: Distance (in graph); complement (of graph); Wiener index; hyper-Wiener index

DOI: 10.5937/SPSUNP1601035G

Download full text in PDF

Abstract:

Let G be a graph with n vertices and m edges. In many cases the complement of G has the following properties: it is connected, its diameter is 2, its Wiener index is equal to (n 2) + m, and its hyper-Wiener index is equal to (n 2) + 2m. We characterize the graphs whose complements have the mentioned properties.