New benchmarks for large-scale networks with given maximum degree and diameter

Loz, Eyal and Pineda Villavicencio, Guillermo 2010, New benchmarks for large-scale networks with given maximum degree and diameter, Computer journal, vol. 53, no. 7, pp. 1092-1105, doi: 10.1093/comjnl/bxp091.

Attached Files
Name Description MIMEType Size Downloads

Title New benchmarks for large-scale networks with given maximum degree and diameter
Author(s) Loz, Eyal
Pineda Villavicencio, GuillermoORCID iD for Pineda Villavicencio, Guillermo
Journal name Computer journal
Volume number 53
Issue number 7
Start page 1092
End page 1105
Total pages 14
Publisher Oxford University Press
Place of publication Oxford, Eng.
Publication date 2010-09
ISSN 0010-4620
Keyword(s) degree/diameter problem
Moore bound
Moore graphs
large-scale networks
small-world networks
vertex duplication
Kronecker product
graph compounding
voltage assignment
polarity graphs
voltage graphs
Cayley graphs
Science & Technology
Computer Science, Hardware & Architecture
Computer Science, Information Systems
Computer Science, Software Engineering
Computer Science, Theory & Methods
Computer Science
diameter problem
Summary Large-scale networks have become ubiquitous elements of our society. Modern social networks, supported by communication and travel technology, have grown in size and complexity to unprecedented scales. Computer networks, such as the Internet, have a fundamental impact on commerce, politics and culture. The study of networks is also central in biology, chemistry and other natural sciences. Unifying aspects of these networks are a small maximum degree and a small diameter, which are also shared by many network models, such as small-world networks. Graph theoretical methodologies can be instrumental in the challenging task of predicting, constructing and studying the properties of large-scale networks. This task is now necessitated by the vulnerability of large networks to phenomena such as cross-continental spread of disease and botnets (networks of malware). In this article, we produce the new largest known networks of maximum degree 17 ≤ Δ ≤ 20 and diameter 2 ≤ D ≤ 10, using a wide range of techniques and concepts, such as graph compounding, vertex duplication, Kronecker product, polarity graphs and voltage graphs. In this way, we provide new benchmarks for networks with given maximum degree and diameter, and a complete overview of state-of-the-art methodology that can be used to construct such networks.
Language eng
DOI 10.1093/comjnl/bxp091
Indigenous content off
Field of Research 08 Information and Computing Sciences
HERDC Research category C1.1 Refereed article in a scholarly journal
Copyright notice ©2009, The Author
Persistent URL

Connect to link resolver
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 6 times in TR Web of Science
Scopus Citation Count Cited 5 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 64 Abstract Views, 2 File Downloads  -  Detailed Statistics
Created: Tue, 25 Jun 2019, 11:47:13 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact