Counterexamples to the Henning--Yeo Conjecture: Unbounded Fixed-Degree Gaps and Sharp First-Order Asymptotics
Henning and Yeo conjectured an upper bound on the identifying vertex cover number of a graph in terms of its order, size, and maximum degree. A two-parameter family $H_{t,r}$ of connected diameter-two graphs disproves the bound for every maximum degree at least four; after denominators are cleared, its margin is exactly $-(t-1)(r-1)$. The complement relation $τ_D=n-ρ$ exposes the mechanism: diameter-two fibres admit at most one packing vertex, while degree deficit accumulates under tree gluing with controlled port loads. Writing $A_Δ$ for the supremal additive gap at maximum degree exactly…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.19455
curl -X POST /api/v1/records/arxiv/2608.19455/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.19455/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'