Paperlane

no. 12 · Tuesday 10 November 2026

Extremal graphs for Alon's graph coupon-collector conjecture

Xingchao Deng and Guoqing Wang

math.CO · 15 pp

Abstract

Let \(G\) be a finite simple graph without isolated vertices. Starting with every vertex uncovered, at each step sample a vertex uniformly and independently and cover one of its uncovered neighbors, chosen uniformly, if any. Let \(\cc(G)\) denote the expected number of steps required to cover all vertices. Alon conjectured that disjoint unions of \(K_{d+1}\) maximize \(\cc(G)\) among \(d\)-regular graphs of a prescribed order whenever such unions exist. In this paper, we disprove this conjecture for every fixed \(d\ge2\) and give a complete characterization of the extremal graphs for \(d=2\) at every order \(n\ge3\). In particular, all but at most six vertices of any such extremal graph lie in four-cycle components.

comments
15pages
fields
Combinatorics
pdf ↗ page arXiv:2611.11345 ↗