On the radius of neighborhood graphs

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

Full description

Saved in:
Bibliographic Details
Published in:Quaestiones mathematicae 2016-08, Vol.39 (5), p.577-585
Main Authors: Mukwembi, Simon, Vetrík, Tomáš
Format: Article
Language:English
Subjects:
Graphs
k-step graph
Neighborhood graph
Neighborhoods
radius
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 .
ISSN:1607-3606
1727-933X
DOI:10.2989/16073606.2015.1113211