Main Article Content
On the radius of neighborhood graphs
Abstract
The k-step graph G′k of a graph G has the same vertex set as G and two vertices are adjacent in G ′ k if and only if there exists a path of length k connecting them in G. The graph G ′ 2 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 G ′ 2 we state bounds on the radius of G ′ 2 in terms of the radius of G and we show that the bounds are sharp. For disconnected graphs G′ 2, we give exact values of the radii of components of G ′2.
Mathematics Subject Classication (2010): 05C12, 05C35.
Key words: Neighborhood graph, k-step graph, radius.
