## 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∩T ≠ 0 for every edge e in G and e∩T ≠ f∩T for every two distinct edges e and f in G. The identifying vertex cover number T_{D}(G) of G is the minimum size of an identifying vertex cover in G. We observe that T_{D}(G)+ρ(G) = |V (G)|, where ρ(G) denotes the packing number of G. We conjecture that if G is a graph of order n and size m with maximum degree Δ, then T_{D}(G) ≤(Δ(Δ-1)/ Δ^{2}+1)n + (2/Δ^{2}+1) m. If the conjecture is true, then the bound is best possible for all Δ ≥ 1. We prove this conjecture when Δ ≥ 1 and G is a Δ-regular graph. The three known Moore graphs of diameter 2, 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 Δ∈ {2; 3}.

Original language | English |
---|---|

Journal | Electronic Journal of Combinatorics |

Volume | 19 |

Issue number | 4 |

DOIs | |

Publication status | Published - 6 Dec 2012 |

## Keywords

- Identifying vertex cover
- Transversal
- Vertex cover

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics