## Abstract

The open neighborhood N(v) of a vertex v in a graph G is the set of vertices adjacent to v in G. A graph is twin-free (or open identifiable) if every two distinct vertices have distinct open neighborhoods. A separating open code in G is a set C of vertices such that N(u) ∩ C ≠ N(v) ∩ C for all distinct vertices u and v in G. An open dominating set, or total dominating set, in G is a set C of vertices such that N(u) ∩ C ≠ N(v) ∩ C for all vertices v in G. An identifying open code of G is a set C that is both a separating open code and an open dominating set. A graph has an identifying open code if and only if it is twin-free. If G is twin-free, we denote by γ^{IOC}(G) the minimum cardinality of an identifying open code in G. A hypergraph H is identifiable if every two edges in H are distinct. A distinguishing-transversal T in an identifiable hypergraph H is a subset T of vertices in H that has a nonempty intersection with every edge of H (that is, T is a transversal in H) such that T distinguishes the edges, that is, e ∩ T ≠ f ∩ T for every two distinct edges e and f in H. The distinguishing-transversal number τ_{D}(H) of H is the minimum size of a distinguishing-transversal in H. We show that if H is a 3-uniform identifiable hypergraph of order n and size m with maximum degree at most 3, then 20τ_{D}(H) ≤ 12n + 3m. Using this result, we then show that if G is a twin-free cubic graph on n vertices, then γ^{IOC}(G) ≤ 3n/4. This bound is achieved, for example, by the hypercube.

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

Pages (from-to) | 909-932 |

Number of pages | 24 |

Journal | Graphs and Combinatorics |

Volume | 30 |

Issue number | 4 |

DOIs | |

Publication status | Published - Jun 2014 |

## Keywords

- Distinguishing transversals
- Hypergraphs
- Identifying opencodes
- Total domination

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics