TY  - JOUR
A1  - Lokot, Tatiana
A1  - Mehler, Alexander
A1  - Abramov, Olga
T1  - On the limit value of compactness of some graph classes
T2  - PLoS one
N2  - In this paper, we study the limit of compactness which is a graph index originally introduced for measuring structural characteristics of hypermedia. Applying compactness to large scale small-world graphs (Mehler, 2008) observed its limit behaviour to be equal 1. The striking question concerning this finding was whether this limit behaviour resulted from the specifics of small-world graphs or was simply an artefact. In this paper, we determine the necessary and sufficient conditions for any sequence of connected graphs resulting in a limit value of CB = 1 which can be generalized with some consideration for the case of disconnected graph classes (Theorem 3). This result can be applied to many well-known classes of connected graphs. Here, we illustrate it by considering four examples. In fact, our proof-theoretical approach allows for quickly obtaining the limit value of compactness for many graph classes sparing computational costs.
KW  - Geodesics
KW  - Graph theory
KW  - Hypertext
KW  - Sequence analysis
Y1  - 2018
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/47857
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-478579
SN  - 1932-6203
N1  - Copyright: © 2018 Lokot et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
VL  - 13
IS  - (11): e0207536
SP  - 1
EP  - 8
PB  - PLoS
CY  - Lawrence, Kan.
ER  -