Identifying vertex covers in graphs (Q1953340)

Summary: 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 \neq \emptyset\) for every edge \(e\) in \(G\) and \(e \cap T \neq 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) \leq \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 \geq 1\). We prove this conjecture when \(\Delta \geq 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\}\).