Identifying Vertex Covers in Graphs

Source abstract

An identifying vertex cover in a graph $G$ is a subset $T$ of vertices in $G$ that has a nonempty intersection with every edge of $G$ such that $T$ distinguishes the edges, that is, $e \cap T \ne \emptyset$ for every edge $e$ in $G$ and $e \cap T \ne f \cap T$ for every two distinct edges $e$ and $f$ in $G$. The identifying vertex cover number $\tau_D(G)$ of $G$ is the minimum size of an identifying vertex cover in $G$. We observe that $\tau_D(G) + \rho(G) = |V(G)|$, where $\rho(G)$ denotes the packing number of $G$. We conjecture that if $G$ is a graph of order $n$ and size $m$ with maximum degree $\Delta$, then $\tau_D(G) \le \left( \frac{\Delta(\Delta - 1)}{\Delta^2 + 1} \right) n + \left( \frac{2}{\Delta^2 + 1} \right) m$. If the conjecture is true, then the bound is best possible for all $\Delta \ge 1$. We prove this conjecture when $\Delta \ge 1$ and $G$ is a $\Delta$-regular graph. The three known Moore graphs of diameter two, namely the $5$-cycle, the Petersen graph and the Hoffman-Singleton graph, are examples of regular graphs that achieves equality in the upper bound. We also prove this conjecture when $\Delta \in \{2,3\}$.