## Abstrakt

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}.

Originalsprog | Engelsk |
---|---|

Artikelnummer | 32 |

Tidsskrift | Electronic Journal of Combinatorics |

Vol/bind | 19 |

Udgave nummer | 4 |

Antal sider | 13 |

ISSN | 1097-1440 |

Status | Udgivet - 2012 |

Udgivet eksternt | Ja |