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