Distance-locally disconnected graphs

For an integer k ≥ 1, we say that a (finite simple undirected) graph <i>G</i> is <i>k</i>-distance-locally disconnected, or simply <i>k</i>-locally disconnected if, for any x ∈ V(<i>G</i>), the set of vertices at distance at least 1 and at most <i>k</i> from <i>x</i> induces in <i>G</i> a disconnected graph. In this paper we study the asymptotic behavior of the number of edges of a <i>k</i>-locally disconnected graph on <i>n</i> vertices. For general graphs, we show that this number is Θ(n²) for any fixed value of <i>k</i> and, in the special case of regular graphs, we show that this asymptotic rate of growth cannot be achieved. For regular graphs, we give a general upper bound and we show its asymptotic sharpness for some values of <i>k</i>. We also discuss some connections with cages.