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.

DOI: https://doi.org/10.1016/j.jctb.2018.07.002

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.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 56279
• Item Type
• Journal Item
• ISSN
• 0095-8956
• Project Funding Details

• Funded Project Name	Project ID	Funding Body
  Not Set	APVV 0136/12	Not Set
  Not Set	APVV15-0220	Not Set
  Not Set	VEGA 1/0007/14	Not Set
  Not Set	VEGA 1/0026/16	Not Set
  Not Set	VEGA 1/0142/17	Not Set

• Keywords
• degree; diameter; vertex-transitive graphs; Moore bound; order estimates
• 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
• © 2018 Elsevier
• Depositing User
• Jozef Širáň