**Second Meeting**

Date: June 22-24, 2009

Location : room F111, Université Joseph Fourier, Grenoble, France

## Schedule of the meeting

### Monday

- 10h-12h: A. Parreau - "dynamic radius codes in the cycle"
- 12h30: lunch
- 14h-17h: L. Beaudou - PhD defense

### Tuesday

- 9h-10h30: F. Foucaud - "identifying codes and the maximum degree"
- 10h30-12h: discussion
- 12h30: lunch
- 14h-15h30: A. Pêcher - "linear programming for identifying codes"
- 15h30 - 18h: discussion
- 20h: dinner

### Wednesday

- 10h-11h: open discussion
- 11h-12h30: E. Sopena - "identifying codes in evolving graphs"
- 13h: lunch
- 14h-16h: open discussion

## Minutes of the meeting

** Participants**: L. Beaudou, P. Dorbec, F. Foucaud, S. Gravier, R. Klasing, A. Parreau, A. Pêcher, A. Raspaud, E. Sopena

*Monday*

- 10h-12h:
definitions of two generalizations of r-identifying codes (IC) with dynamic radius - weak r-identifying codes (WIC) and half-weak r-identifying codes (HWIC). WICs generalize ICs and HWICs generalize WICs. Weak 1-identifying codes are equivalent to locating-dominating sets. Optimal cardinalities of WICs and HWICs in the cycle Cn are given.*A. Parreau: dynamic radius codes in the cycle*

*Tuesday*

- 9h-10h30:
known lower bound for the minimum cardinality of a 1-identifying code in graphs of maximum degree Delta - characterization and construction of all graphs reaching this bound - general upper bound for the minimum cardinality of a 1-identifying code - several upper bounds for this value with respect to the maximum degree in the general case, in regular graphs, in triangle-free graphs, in graphs of girth at least 5, and in subcubic graphs*F. Foucaud: identifying codes and the maximum degree* - 10h30-12h:
1-identifying codes in Sierpinski graphs - 1-identifying codes in products of graphs: products of paths, products of cycles (tori), products of a path and a clique*discussion* - 14h-15h30:
presentation of constraints for linear programmes used for computing optimal ICs, WICs and HWICs - using continuous variables to characterize IC polytopes - relationship with weighted ICs - usefulness for lower bounds on discrete ICs*A. Pêcher: linear programming for identifying codes* - 15h30-18h:
1-identifying codes in some circulant graphs*discussion*

*Wednesday*

- 10h-11h:
locating sets (Slater, 1975) allow identification of vertices using distances - relationship between locating sets and Half Weak r-identifying codes: a locating set is a Half Weak diam(G)-identifying code - locating sets in trees, cycles, chains - graphs for which an optimal locating set has cardinality 1 or 2 - locating colorings (Slater et. al, 2002) - relationship between locating sets, the locating chromatic number and the chromatic number: is it easy to construct a locating-coloring using a locating set?*discussion* - 11h-12h30:
identifying codes in increasing paths - use of local rewriting rules to construct dynamic identifying codes - use of distributed local algorithms - termination and convergence time of the algorithm, optimality ratios*E. Sopena: identifying codes in evolving graphs* - 14h-16h:
organizational questions: report, next meeting in autumn*discussion*