### Resumé

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 |

### Fingeraftryk

### Citer dette

*Electronic Journal of Combinatorics*,

*19*(4), [32].

}

*Electronic Journal of Combinatorics*, bind 19, nr. 4, 32.

**Identifying vertex covers in graphs.** / Henning, Michael A.; Yeo, Anders.

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

TY - JOUR

T1 - Identifying vertex covers in graphs

AU - Henning, Michael A.

AU - Yeo, Anders

PY - 2012

Y1 - 2012

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

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

KW - Identifying vertex cover

KW - Transversal

KW - Vertex cover

M3 - Journal article

VL - 19

JO - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

SN - 1097-1440

IS - 4

M1 - 32

ER -