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

About 14 years old · traced to

For fixed d≥3d\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 d≥3d\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.