• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On Graphs Admitting Codes Identifying Sets of Vertices

Tero Laihonen, Julien Moncel, On Graphs Admitting Codes Identifying Sets of Vertices. Australasian Journal of Combinatorics 41, 81–91, 2008.

Abstract:

Let G = (V,E) be a graph and N[X] denote the closed neighbourhood of X ⊆ V , that is to say, the union of X with the set of vertices which are adjacent to X. Given an integer t ≥ 1, a subset of vertices C ⊆ V is said to be a code identifying sets of at most t vertices of G—or, for short, a t-set-ID code of G—if the sets N[X] ∩ C are all distinct, when X runs through subsets of at most t vertices of V . A graph G admits a t-set-ID code if and only if N[X] 6= N[Y ] for all pairs X and Y which are distinct subsets of at most t vertices of V .

Graphs admitting identifying codes is a recent topic. In this paper, we show that for G1 admitting a t1-set-ID code, and G2 admitting a t2- set-ID code, the cartesian product G1G2 admits a max{t1, t2}-set-ID code, and we show that this result is the best possible. We also study the extremal question of minimizing the number of vertices of a graph admitting a t-set-ID code. Asymptotically, this number is (t2), and we give an explicit construction of an infinite family of t-regular graphs attaining this bound. The construction uses so-called distance-regular graphs.

BibTeX entry:

@ARTICLE{jLaMo08a,
  title = {On Graphs Admitting Codes Identifying Sets of Vertices},
  author = {Laihonen, Tero and Moncel, Julien},
  journal = {Australasian Journal of Combinatorics},
  volume = {41},
  publisher = {University of Queensland},
  pages = {81–91},
  year = {2008},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication