Šiagiová, Jana and Siran, Jozef
(2012).
Approaching the Moore bound for diameter two by Cayleygraphs.
Journal of Combinatorial Theory, Series B, 102(2) pp. 470–473.
Full text available as:
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: |
Journal Article
|
| Copyright Holders: |
2011 Elsevier |
| ISSN: |
0095-8956 |
| External 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/Department: |
Mathematics, Computing and Technology > Mathematics and Statistics |
| Item ID: |
32158 |
| Depositing User: |
Jozef Siran
|
| Date Deposited: |
03 Feb 2012 11:28 |
| Last Modified: |
28 Aug 2013 08:34 |
| URI: |
http://oro.open.ac.uk/id/eprint/32158 |
Actions (login may be required)
