Šiagiová, Jana and Siran, Jozef
(2012).
|
Due to copyright restrictions, this file is not available for public download Click here to request a copy from the OU Author. |
| DOI (Digital Object Identifier) Link: | https://doi.org/10.1016/j.jctb.2011.07.005 |
|---|---|
| Google Scholar: | Look up in Google Scholar |
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).
| Item Type: | Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Copyright Holders: | 2011 Elsevier | ||||||||||||
| ISSN: | 0095-8956 | ||||||||||||
| Project Funding Details: |
|
||||||||||||
| Keywords: | degree; diameter; Moore bound; Cayley graph | ||||||||||||
| Academic Unit/School: | Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics Faculty of Science, Technology, Engineering and Mathematics (STEM) |
||||||||||||
| Item ID: | 32158 | ||||||||||||
| Depositing User: | Jozef Širáň | ||||||||||||
| Date Deposited: | 03 Feb 2012 11:28 | ||||||||||||
| Last Modified: | 06 Oct 2016 04:53 | ||||||||||||
| URI: | http://oro.open.ac.uk/id/eprint/32158 | ||||||||||||
| Share this page: |     |
Altmetrics | Scopus Citations |