PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2013 | 33 | 1 | 203-215
Tytuł artykułu

Distance-Locally Disconnected Graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
33
Numer
1
Strony
203-215
Opis fizyczny
Daty
wydano
2013-03-01
online
2013-04-13
Twórcy
autor
  • University of Newcastle, Australia University of West Bohemia, Pilsen, Czech Republic King’s College, London, UK ITB Bandung, Indonesia, mirka.miller@newcastle.edu.au
autor
  • University of West Bohemia, Pilsen, Czech Republic Institute for Theoretical Computer Science, Pilsen, Czech Republic University of Newcastle, Australia, ryjacek@kma.zcu.cz
Bibliografia
  • [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.
  • [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[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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1657
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.