- Tytuł:
- Distance-Locally Disconnected Graphs
- Autorzy:
-
Miller, Mirka
Ryan, Joe
Ryjáček, Zdeněk - Powiązania:
- https://bibliotekanauki.pl/articles/30146681.pdf
- Data publikacji:
- 2013-03-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
neighborhood
distance
locally disconnected
cage - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2013, 33, 1; 203-215
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł