On the radius of neighborhood graphs. Issue 5 (11th August 2016) - Mukwembi, Simon; Vetrík, Tomáš
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 .