On the radius of neighborhood graphs

Abstract

The k-step graph of a graph G has the same vertex set as G and two vertices are adjacent in if and only if there exists a path of length k connecting them in G. The graph is called the neighborhood graph of G. We present results on the connectivity and the radius of k-step graphs, especially on the radius of neighborhood graphs. For connected graphs we state bounds on the radius of in terms of the radius of G and we show that the bounds are sharp. For disconnected graphs , we give exact values of the radii of components of .