Delphi.science

Extremal graphs for Alon's graph coupon-collector conjecture

Source: arxiv.org/abs/2611.11345

Xingchao Deng, Guoqing Wang

arXivarxiv/2611.11345Nov 8, 2026math.COscore 0

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\)…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'