DISTANCE-LOCALLY DISCONNECTED GRAPHS

作者：Miller Mirka^*; Ryan Joe; Ryjacek Zdenek

来源：Discussiones Mathematicae - Graph Theory, 2013, 33(1): 203-215.

DOI：10.7151/dmgt.1657

• neighborhood
• distance
• locally disconnected
• cage

For an integer k %26gt;= 1, we say that a (finite simple undirected) graph G is k-distance-locally disconnected, or simply k-locally disconnected if, for any x is an element of V(G), the set of vertices at distance at least 1 and at most k from x induces in G a disconnected graph. In this paper we study the asymptotic behavior of the number of edges of a k-locally disconnected graph on n vertices. For general graphs, we show that this number is circle minus(n(2)) for any fixed value of k 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 k. We also discuss some connections with cages.

• 出版日期2013