
doi: 10.37236/2114
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\}$.
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), transversal, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Transversal (matching) theory, identifying vertex cover, vertex cover
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), transversal, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Transversal (matching) theory, identifying vertex cover, vertex cover
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
