Format

Send to

Choose Destination
PLoS One. 2018 Nov 20;13(11):e0207536. doi: 10.1371/journal.pone.0207536. eCollection 2018.

On the limit value of compactness of some graph classes.

Author information

1
Retired, Faculty of Mathematics, Bielefeld University, Bielefeld, Germany.
2
Affiliation Faculty of Computer Science and Mathematics, Goethe-University Frankfurt, Frankfurt, Germany.
3
Affiliation CITEC/Faculty of Technology, Bielefeld University, Bielefeld, Germany.

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 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.

PMID:
30458027
PMCID:
PMC6245735
DOI:
10.1371/journal.pone.0207536
[Indexed for MEDLINE]
Free PMC Article

Supplemental Content

Full text links

Icon for Public Library of Science Icon for PubMed Central
Loading ...
Support Center