The Computer Journal Advance Access published online on November 4, 2009
The Computer Journal, doi:10.1093/comjnl/bxp091
New Benchmarks for Large-Scale Networks with Given Maximum Degree and Diameter
1 Department of Mathematics, University of Auckland, Auckland, New Zealand
2 Centre for Informatics and Applied Optimization, University of Ballarat, Ballarat, VIC 3353, Australia
* Corresponding author: work{at}guillermo.com.au
Received 5 July 2009; revised 30 September 2009
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.
Key Words: 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