# Identifying vertex covers in graphs

Michael A. Henning, Anders Yeo

Research output: Contribution to journalJournal articleResearchpeer-review

## 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 TD(G) of G is the minimum size of an identifying vertex cover in G. We observe that TD(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 TD(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 32 Electronic Journal of Combinatorics 19 4 13 1097-1440 Published - 2012 Yes

## Keywords

• Identifying vertex cover
• Transversal
• Vertex cover

## Fingerprint

Dive into the research topics of 'Identifying vertex covers in graphs'. Together they form a unique fingerprint.