Distinguishing-Transversal in Hypergraphs and Identifying Open Codes in Cubic Graphs

Michael A. Henning, Anders Yeo

Research output: Contribution to journalJournal articleResearchpeer-review

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 languageEnglish
JournalGraphs and Combinatorics
Volume30
Issue number4
Pages (from-to)909-932
ISSN0911-0119
DOIs
Publication statusPublished - 2014
Externally publishedYes

Keywords

  • Distinguishing transversals
  • Hypergraphs
  • Identifying opencodes
  • Total domination

Fingerprint

Dive into the research topics of 'Distinguishing-Transversal in Hypergraphs and Identifying Open Codes in Cubic Graphs'. Together they form a unique fingerprint.

Cite this