Discussiones Mathematicae Graph Theory 33(1) (2013) 203-215
doi: 10.7151/dmgt.1657

Dedicated to Mietek Borowiecki on the occasion of his seventieth birthday

[BIBTex] [PDF] [PS]

Distance-locally Disconnected Graphs

Mirka Miller

University of Newcastle, Australia
University of West Bohemia, Pilsen, Czech Republic
King's College, London, UK
ITB Bandung, Indonesia

Joe Ryan

University of Newcastle, Australia

Zdeněk Ryjáček

University of West Bohemia, Pilsen, Czech Republic
Institute for Theoretical Computer Science, Pilsen, Czech Republic
University of Newcastle, Australia


For an integer k ≥ 1, we say that a (finite simple undirected) graph G is k-distance-locally disconnected, or simply if, for any x ∈ 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 on n vertices. For general graphs, we show that this number is Θ(n2) 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.

Keywords: neighborhood, distance, locally disconnected, cage

2010 Mathematics Subject Classification: 05C35.


[1]J.A. Bondy, U.S.R. Murty, Graph Theory (Springer, NewYork, 2008).
[2]G. Exoo and R. Jajcay, Dynamic cage survey, Electron. J. Combin. 18 (2011) #DS16.
[3]F. Lazebnik, V.A. Ustimenko and A.J. Woldar, New upper bounds on the order of cages, Electron. J. Combin. 4(2) (1977) R13.
[4]L. Lovász, J. Pelikán and K. Vesztergombi, Discrete Mathematics: Elementary and Beyond (Springer, NewYork, 2003).
[5]Z. Ryjáček, N2-locally disconnected graphs, Discrete Math. 121 (1993) 189--193, doi: 10.1016/0012-365X(93)90551-4.
[6]Z. Ryjáček and B. Zelinka, Locally disconnected graphs with large numbers of edges, Math. Slovaca 37(2) (1987) 195--198.
[7]B. Zelinka, Two local properties of graphs, Časop. Pěst. Mat. 113 (1988) 113--121.

Received 16 April 2012
Revised 2 November 2012
Accepted 5 November 2012