PDF
Discussiones Mathematicae Graph Theory 33(1) (2013)
203-215
DOI: https://doi.org/10.7151/dmgt.1657
Dedicated to Mietek Borowiecki on the occasion of his seventieth birthday
Distance-locally Disconnected Graphs
| Mirka Miller
University of Newcastle, Australia | Joe Ryan University of Newcastle, Australia | Zdeněk Ryjáček
University of West Bohemia, Pilsen, Czech Republic |
Abstract
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.
References
| [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
Close