pipette
ESEspañol

Extremal graphs for Alon's graph coupon-collector conjecture

Xingchao Deng, Guoqing Wang

Preprint

In the authors' words

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.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 15pages