On the nonexistence of graphs of diameter 2 and defect 2
- Authors: Miller, Mirka , Nguyen, Minh Hoang , Pineda-Villavicencio, Guillermo
- Date: 2009
- Type: Text , Journal article
- Relation: The Journal of Combinatorial Mathematics and Combinatorial Computing Vol. 71, no. (2009), p. 5-20
- Full Text: false
- Reviewed:
- Description: In 1960, Hoffman and Singleton investigated the existence of Moore graphs of diameter 2 (graphs of maximum degree d and d² + 1 vertices), and found that such graphs exist only for d = 2; 3; 7 and possibly 57. In 1980, Erdös et al., using eigenvalue analysis, showed that, with the exception of C4, there are no graphs of diameter 2, maximum degree d and d² vertices. In this paper, we show that graphs of diameter 2, maximum degree d and d² - 1 vertices do not exist for most values of d with d ≥ 6, and conjecture that they do not exist for any d ≥ 6.
- Description: 2003007893
On the non-existence of even degree graphs of diameter 2 and defect 2
- Authors: Miller; Mirka , Nguyen, Minh Hoang , Pineda-Villavicencio, Guillermo
- Date: 2007
- Type: Text , Conference paper
- Relation: Paper presented at 18th International Workshop on Combinatorial Algorithms, IWOCA 2007, Rafferty's Resort, Lake Macquarie, New South Wales : 5th-9th November 2007
- Full Text:
- Description: Using eigenvalue analysis, it was shown by Erdos et al. that, with the exception of C4, there are no graphs of diameter 2, maximum degree d and d2 vertices. In this paper, we show that graphs of diameter 2, maximum degree d and d2-1 vertices do not exist for most values of d, when d is even, and we conjecture that they do not exist for any even d greater than 4.
- Description: 2003007893
Complete catalogue of graphs of maximum degree 3 and defect at most 4
- Authors: Miller, Mirka , Pineda-Villavicencio, Guillermo
- Date: 2009
- Type: Text , Journal article
- Relation: Discrete Applied Mathematics Vol. 157, no. 13 (2009), p. 2983-2996
- Full Text:
- Reviewed:
- Description: We consider graphs of maximum degree 3, diameter D≥2 and at most 4 vertices less than the Moore bound M3,D, that is, (3,D,−)-graphs for ≤4. We prove the non-existence of (3,D,−4)-graphs for D≥5, completing in this way the catalogue of (3,D,−)-graphs with D≥2 and ≤4. Our results also give an improvement to the upper bound on the largest possible number N3,D of vertices in a graph of maximum degree 3 and diameter D, so that N3,D≤M3,D−6 for D≥5. Copyright Elsevier.
New benchmarks for large-scale networks with given maximum degree and diameter
- Authors: Loz, Eyal , Pineda-Villavicencio, Guillermo
- Date: 2010
- Type: Text , Journal article
- Relation: Computer Journal Vol. 53, no. 7 (2010), p. 1092-1105
- Full Text: false
- Reviewed:
- Description: 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.