Connected Counterexamples to the Henning--Yeo Conjecture on Identifying Vertex Covers

Abstract

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. We disprove the conjectured inequality with a two-parameter family $H_{t,r}$ of connected diameter-two graphs. After clearing denominators, the right-hand side minus the left-hand side is exactly $-(t-1)(r-1)$; hence a connected counterexample exists for every maximum degree at least four. Chaining copies through low-degree vertices preserves the maximum degree and allows the packing number to be determined exactly. At maximum degree five, this gives counterexamples of arbitrarily large order with additive gap $1/13$. For every fixed maximum degree $Δ\ge6$, suitable chains have unbounded additive violation. Thus neither rounding nor a fixed additive correction repairs the conjecture. The supremal normalized additive gap at maximum degree $Δ$ is $Θ(1/Δ)$. An exhaustive check of all graphs of order at most seven shows that the eight-vertex example $H_{2,2}$ has minimum possible order.

Disclosure

“tants c∆ in Theorem 6.2, resolving unboundedness in degrees four and five, and testing whether any of the blocks are extremal for c∆ are concrete directions for further work. AI-assistance disclosure Generative-AI tools were used extensively for exploratory search, proposing candidate constructions and proof arguments, code development, assistance with literature searches, drafting, and language editing. No AI system is an author. The author independently”

PDF page 11

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-22T03:01:08.554481Z

Structural counts