Journalartikel - Artikel | | Peer reviewed Open Access

On the limit value of compactness of some graph classes

Autor(en)
Lokot, Tatiana ; Mehler, Alexander ; Abramov, Olga 0000-0002-6547-1415
Normierter Zeitschriftentitel
PLOS ONE 
DOI
10.1371/journal.pone.0207536
ISSN
1932-6203
PubMed-ID
30458027
URN
urn:nbn:de:0070-pub-29321192
URL
https://pub.uni-bielefeld.de/record/2932119
Web of Science-ID
000450775300026

Weitere Details

Sprache
englisch
Darstellungsform
Text
Band
13
Artikelnummer
e0207536
Ausgabe
11
Schlagwörter
compactness of graphs , network theory
Link zum Volltext (intern)
https://pub.uni-bielefeld.de/record/2932119
DDC
150

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 [1] 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_B = 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.

Zitierstile

Download
 RDF/XML-Format
 JSON-LD-Format
 Turtle-Format
 N3-Format