Domination and 2-degree-packing numbers in graphs

Abstract

A dominating set of a graph $G$ is a set $D\subseteq V(G)$ such that \-every vertex of $G$ is either in $D$ or is adjacent to a vertex in $D$. The domination number of $G$, $\gamma (G)$, is the minimum order of a dominating set. A subset $R$ of edges of a graph $G$ is a 2-degree-packing, if any three edges from $R$ do not have the same incident vertex. The 2-degree-packing number of $G$, ${\nu }_2(G)$, is the maximum order of a 2-degree-packing of $G$. In this paper, we prove that any simple graph $G$ satisfies $\gamma (G)\le {\nu }_2(G)-1$. Furthermore, we give a characterization of simple connected graphs $G$ satisfying $\gamma (G)={\nu }_2(G)-1$.