Back to Search
Start Over
On the limit value of compactness of some graph classes.
- Source :
- PLoS ONE; 11/20/2018, Vol. 13 Issue 11, p1-8, 8p
- Publication Year :
- 2018
-
Abstract
- 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 C<subscript>B</subscript> = 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 19326203
- Volume :
- 13
- Issue :
- 11
- Database :
- Complementary Index
- Journal :
- PLoS ONE
- Publication Type :
- Academic Journal
- Accession number :
- 133109994
- Full Text :
- https://doi.org/10.1371/journal.pone.0207536