On the limit value of compactness of some graph classes.
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 thi...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2018-01-01
|
| Series: | PLoS ONE |
| Online Access: | http://europepmc.org/articles/PMC6245735?pdf=render |
| _version_ | 1819038588079177728 |
|---|---|
| author | Tatiana Lokot Alexander Mehler Olga Abramov |
| author_facet | Tatiana Lokot Alexander Mehler Olga Abramov |
| author_sort | Tatiana Lokot |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-21T08:39:41Z |
| format | Article |
| id | doaj.art-76ba438913684c8fa310c2bfc7dd6e02 |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-12-21T08:39:41Z |
| publishDate | 2018-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-76ba438913684c8fa310c2bfc7dd6e022022-12-21T19:09:58ZengPublic Library of Science (PLoS)PLoS ONE1932-62032018-01-011311e020753610.1371/journal.pone.0207536On the limit value of compactness of some graph classes.Tatiana LokotAlexander MehlerOlga AbramovIn 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.http://europepmc.org/articles/PMC6245735?pdf=render |
| spellingShingle | Tatiana Lokot Alexander Mehler Olga Abramov On the limit value of compactness of some graph classes. PLoS ONE |
| title | On the limit value of compactness of some graph classes. |
| title_full | On the limit value of compactness of some graph classes. |
| title_fullStr | On the limit value of compactness of some graph classes. |
| title_full_unstemmed | On the limit value of compactness of some graph classes. |
| title_short | On the limit value of compactness of some graph classes. |
| title_sort | on the limit value of compactness of some graph classes |
| url | http://europepmc.org/articles/PMC6245735?pdf=render |
| work_keys_str_mv | AT tatianalokot onthelimitvalueofcompactnessofsomegraphclasses AT alexandermehler onthelimitvalueofcompactnessofsomegraphclasses AT olgaabramov onthelimitvalueofcompactnessofsomegraphclasses |