Covering and 2-degree-packing numbers in graphs

Abstract

In this paper, we give a relationship between the covering number of a simple graph $G$, $\beta (G)$, and a new parameter associated to $G$ which is called 2-degree-packing number of $G$, ${\nu }_2(G)$. We prove that$$\lceil {\nu }_2(G)/2\rceil \le \beta (G)\le {\nu }_2(G)-1,$$ for any connected simple graph $G$, with $|E(G)|>{\nu }_2(G)$, and we give a characterization of simple connected graphs which attains the inequalities.