- Title
- Distance-locally disconnected graphs
- Creator
- Miller, Mirka; Ryan, Joe; Ryjáček, Zdeněk
- Relation
- Discussiones Mathematicae: Graph Theory Vol. 33, Issue 1, p. 203-215
- Publisher Link
- http://dx.doi.org/10.7151/dmgt.1657
- Publisher
- Institute of Mathematics, Technical University Zielona Gora
- Resource Type
- journal article
- Date
- 2013
- Description
- 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 Θ(n²) 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.
- Subject
- neighbourhood; distance; locally disconnected; cage
- Identifier
- http://hdl.handle.net/1959.13/1311573
- Identifier
- uon:22237
- Identifier
- ISSN:1234-3099
- Language
- eng
- Full Text
- Reviewed
- Hits: 2505
- Visitors: 1856
- Downloads: 240
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Publisher version (open access) | 374 KB | Adobe Acrobat PDF | View Details Download |