Distance-Locally Disconnected Graphs
Mirka Miller; Joe Ryan; Zdeněk Ryjáček
Discussiones Mathematicae Graph Theory (2013)
- Volume: 33, Issue: 1, page 203-215
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topMirka Miller, Joe Ryan, and Zdeněk Ryjáček. "Distance-Locally Disconnected Graphs." Discussiones Mathematicae Graph Theory 33.1 (2013): 203-215. <http://eudml.org/doc/268130>.
@article{MirkaMiller2013,
abstract = {For an integer k ≥ 1, we say that a (finite simple undirected) graph G is k-distance-locally disconnected, or simply k-locally disconnected 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 k-locally disconnected graph 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.},
author = {Mirka Miller, Joe Ryan, Zdeněk Ryjáček},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {neighborhood; distance; locally disconnected; cage; neighborhood distance},
language = {eng},
number = {1},
pages = {203-215},
title = {Distance-Locally Disconnected Graphs},
url = {http://eudml.org/doc/268130},
volume = {33},
year = {2013},
}
TY - JOUR
AU - Mirka Miller
AU - Joe Ryan
AU - Zdeněk Ryjáček
TI - Distance-Locally Disconnected Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2013
VL - 33
IS - 1
SP - 203
EP - 215
AB - For an integer k ≥ 1, we say that a (finite simple undirected) graph G is k-distance-locally disconnected, or simply k-locally disconnected 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 k-locally disconnected graph 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.
LA - eng
KW - neighborhood; distance; locally disconnected; cage; neighborhood distance
UR - http://eudml.org/doc/268130
ER -
References
top- [1] J.A. Bondy, U.S.R. Murty, Graph Theory (Springer, NewYork, 2008). doi:10.1007/978-1-84628-970-5[Crossref]
- [2] G. Exoo and R. Jajcay, Dynamic cage survey, Electron. J. Combin. 18 (2011) #DS16. Zbl1169.05336
- [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. Zbl0885.05078
- [4] L. Lovász, J. Pelikán and K. Vesztergombi, Discrete Mathematics: Elementary and Beyond (Springer, NewYork, 2003). Zbl1017.00002
- [5] Z. Ryjáček, N2-locally disconnected graphs, Discrete Math. 121 (1993) 189-193. doi:10.1016/0012-365X(93)90551-4[Crossref]
- [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, ˇ Casop. Pˇest. Mat. 113 (1988) 113-121.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.