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 ${\tau }_D=n-\rho$ 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_{\mathrm{\Delta }}$ for the supremal additive gap at maximum degree exactly $\mathrm{\Delta }$, an exact transfer formula gives $A_{\mathrm{\Delta }}=+\mathrm{\infty }$ for every $\mathrm{\Delta }\ge 4$, using Petersen fibres in degrees four and five and the original $H_{t,r}$ blocks in higher degrees. If $c_{\mathrm{\Delta }}$ denotes the corresponding supremal gap per vertex, rooted rook-graph fibres match a universal square-graph packing bound to first order. Consequently, $c_{\mathrm{\Delta }}\sim 1\mathrm{/}\mathrm{\Delta }$, equivalently $\mathrm{\Delta }{c}_{\mathrm{\Delta }}\to 1$ as $\mathrm{\Delta }\to \mathrm{\infty }$.