A proof of a conjecture on the differential of a subcubic graph

Abstract Let G be a subcubic graph of order n and minimum degree at least 2 . In this paper, we prove the conjecture of Bermudo and Fernau that if n ≥ 23 , then ∂ ( G ) ≥ 5 n ∕ 18 , where ∂ ( G ) is the differential of G . To do this, we use the Gallai-type result involving the Roman domination number γ R ( G ) and ∂ ( G ) by proving that, with the exception of thirteen graphs of order at most 22, every connected graph G satisfies γ R ( G ) ≤ 13 n 18 .