Copy the page URI to the clipboard
Šiagiová, Jana and Siran, Jozef
(2012).
DOI: https://doi.org/10.1016/j.jctb.2011.07.005
Abstract
The order of a graph of maximum degree d and diameter 2 cannot exceed d 2+1, the Moore bound for diameter two. A combination of known results guarantees the existence of regular graphs of degree d, diameter 2, and order at least d2−2d1.525 for all sufficiently large d, asymptotically approaching the Moore bound. The corresponding graphs, however, tend to have a fairly small or trivial automorphism group and the nature of their construction does not appear to allow for modifications that would result in a higher level of symmetry. The best currently available construction of vertex-transitive graphs of diameter 2 and preassigned degree gives order 8/9 (d + ½)2 for all degrees of the form d=(3q−1)/2 for prime powers q=1 mod 4. In this note we show that for an infinite set of degrees d there exist Cayley, and hence vertex-transitive, graphs of degree d, diameter 2, and order d 2−O(d3/2).
Viewing alternatives
Metrics
Public Attention
Altmetrics from AltmetricNumber of Citations
Citations from Dimensions-
Request a copy from the authorVersion of Record (PDF)
This file is not available for public download
Item Actions
Export
About
- Item ORO ID
- 32158
- Item Type
- Journal Item
- ISSN
- 0095-8956
- Project Funding Details
-
Funded Project Name Project ID Funding Body Not Set Not Set VEGA Research Grants [1/0280/10 and 1/0781/11] Not Set Not Set APVV Research Grants [0040-06, 0104-07 and 0223-10] Not Set Not Set APVV LPP Research Grants [0145-06 and 0203-06] - Keywords
- degree; diameter; Moore bound; Cayley graph
- Academic Unit or School
-
Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM) - Copyright Holders
- © 2011 Elsevier
- Depositing User
- Jozef Širáň