**Third Meeting**

Date: November 17-18, 2009

Location : room 178, LaBRI, Bordeaux, France

## Schedule of the meeting

### Tuesday

- 10h: Welcome
- 10h30-11h30: M. Kovse - "Self similar Graphs and Identifying problems"
- 11h30-12h30: Discussion
- 12h30: lunch
- 14h-15h: E. Guerrini - "Identifying vertex coloring"
- 15h-18h: Discussion
- 20h: dinner

### Wednesday

- 10h-11h: F. Foucaud - "Identification with paths"
- 11h-12h: Discussion
- 12h30: lunch
- 14h-15h: A. Parreau - "Generalization of weak and light identifying codes"
- 15h-16h: F. Foucaud - "Online domination, location and identification in trees"

## Minutes of the meeting

** Participants**: O. Delmas, P. Dorbec, F. Foucaud, S. Gravier, E. Guerrini, R. Klasing, M. Kovse, M. Montassier, R. Naserasr, A. Parreau, A. Pêcher (via visioconf.), A. Raspaud, E. Sopena, P. Valicov, G. Zemor.

*Tuesday*

- 10h30-11h30:
*M. Kovse: Self similar Graphs and Identifying problems*

Recall definition of Sierpinski graphs and link with towers of Hanoï - Identifying codes on Sierpinski graphs - definition of self similar graphs (generalization of Sierpinski graphs) - proposition of similar problems than for Sierpinski for self similar graphs : *formal definition (link with wreath product?), adjacency, incidence matrix, identifying codes, chromatic number* - Sierpinski gasket graphs - Regularizing Sierpinski graphs - some geometrical representations of the hypercube.

- 14h-15h:
*E. Guerrini: Identifying vertex coloring*

Definition of identifying chromatic number : min number of colors of a (not necessarily proper) coloring of the vertices such that the set of colors in the neighbourhood of a vertex identifies it - characterize maximum graphs of a class identifyable with a fixed number of colors - identifying chromatic number bounded by size of an identifying code +1 - technique for finding an identifying proper coloring of a path (of good length) that provides almost every triples of colors (describing walks on a complete graph).

*Wednesday*

- 10h-11h:
*F. Foucaud: Identification with paths*

Recall definitions of locating domination, Identifying codes, open neighbourhood locating dominating, locating set/metric base, identification with cycles, with paths - for identifiction with paths, exact value for cliques, hypercubes (log n), cycles and paths, bounds for trees.

- 11h30-12h:
*Problems to be done*

- 14h-15h:
*A.Parreau: Generalization of weak and light identifying codes*

Recall definitions of weak and light identifying codes - generalized definition of Parreau-Identifying codes - results on paths/cycles.

- 15h-16h:
*F.Foucaud: Online Dominating set, locating dominating set, Identifying codes*

Definition of an online algorithm - definition of its performance ratio - recall Eidenbenz results for domination in trees when you may just add vertex at distance 1 - show new algorithm for domination in trees at distance 1 (just add) - locating domination and identifying codes ratios for trees.