McKay–Praeger conjecture for fixed-valency vertex-transitive graphs

From papers

For fixed d3d\geq 3, let VTd(n)VT_d(n) be the number of isomorphism classes of dd-valent vertex-transitive graphs of order at most nn, and let CAYd(n)CAY_d(n) count the corresponding Cayley graphs. McKay–Praeger conjecture. For every d3d\geq 3,

CAYd(n)VTd(n)1(n).\frac{CAY_d(n)}{VT_d(n)}\to 1 \qquad (n\to\infty).

This asserts that almost all fixed-valency vertex-transitive graphs are Cayley graphs. It is presented as an open conjecture; the source attributes the general almost-all formulation to McKay and Praeger.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Primoz Potocnik, Pablo Spiga and Gabriel Verret, “Asymptotic enumeration of vertex-transitive graphs of fixed valency”, arXiv:1210.5736 (2012).

Solutions 0

No solutions have been posted yet.