The 2-Domination Number and the Upper Median Degree: A Proof of Graffiti.pc Conjecture 387

Jun Qing

Let G be a nonempty finite simple graph of order n, and let m(G) be the upper median of its degree sequence. We prove that the 2-domination number satisfies gamma_2(G) <= n - m(G)…