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 languageEnglish
Article number32
JournalElectronic Journal of Combinatorics
Volume19
Issue number4
Number of pages13
ISSN1097-1440
Publication statusPublished - 2012
Externally publishedYes

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.

Cite this