The Open UniversitySkip to content
 

On the defect of vertex-transitive graphs of given degree and diameter

Exoo, Geoffrey; Jajcay, Robert; Mačaj, Martin and Širáň, Jozef (2019). On the defect of vertex-transitive graphs of given degree and diameter. Journal of Combinatorial Theory, Series B, 134 pp. 322–340.

Full text available as:
[img]
Preview
PDF (Accepted Manuscript) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (264kB) | Preview
DOI (Digital Object Identifier) Link: https://doi.org/10.1016/j.jctb.2018.07.002
Google Scholar: Look up in Google Scholar

Abstract

We consider the problem of finding largest vertex-transitive graphs of given degree and diameter. Using two classical number theory results due to Niven and Erdős, we prove that for any fixed degree Δ ≥ 3 and any positive integer δ, the order of a largest vertex-transitive Δ-regular graph of diameter D differs from the Moore bound by more than δ for (asymptotically) almost all diameters D ≥ 2 . We also obtain an estimate for the growth of this difference, or defect, as a function of D.

Item Type: Journal Item
Copyright Holders: 2018 Elsevier
ISSN: 0095-8956
Project Funding Details:
Funded Project NameProject IDFunding Body
Not SetAPVV 0136/12Not Set
Not SetAPVV15-0220Not Set
Not SetVEGA 1/0007/14Not Set
Not SetVEGA 1/0026/16Not Set
Not SetVEGA 1/0142/17Not Set
Keywords: degree; diameter; vertex-transitive graphs; Moore bound; order estimates
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 56279
Depositing User: Jozef Širáň
Date Deposited: 30 Aug 2018 10:41
Last Modified: 29 Jun 2020 10:59
URI: http://oro.open.ac.uk/id/eprint/56279
Share this page:

Metrics

Altmetrics from Altmetric

Citations from Dimensions

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU