Extremal graphs for Alon's graph coupon-collector conjecture
Source: arxiv.org/abs/2611.11345
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\)…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.11345
curl -X POST /api/v1/records/arxiv/2611.11345/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.11345/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'