**Fourth Meeting**

Date: April 14-16, 2010

Location : room 178, LaBRI, Bordeaux, France

## Schedule of the meeting

### Wednesday 14/04/2010

- 11h-12h: Matjaz Kovse - "On identification using paths and related problems"
- 12h30: lunch
- 14h-15h: Eleonora Guerrini - "Hypercubes and identification problems"
- 15h-18h: discussion (open problem session)

### Thursday 15/04/2010

- 10h-11h: Aline Parreau - "Coloring graphs to distinguish (adjacent) vertices"
- 11h-15h: Olivier Delmas - "Some variations of identifying codes"
- 12h30: lunch
- 15h-18h: discussion (session state of the art IDEA)
- 19h30: dinner (villa sud ouest, terminus tram Pessac, 2 av Roger Chaumet, 33600 Pessac)

### Friday 16/04/2010

- 10h-11h: Petru Valicov - "Identifying codes in Hypercubes and projective cubes"
- 11h-12h: Reza Naserasr - "Different proofs of Bondy theorem and identifying codes of directed graphs"
- 12h15: lunch
- 14h-15h: Florent Foucaud - "Extremal cardinalities of identifying codes"
- 15h-16h: open discussion

## Minutes of the meeting

** Participants**: L. Beaudou, C. Charpentier, O. Delmas, P. Dorbec, F. Foucaud, E. Guerrini, R. Klasing, M. Kovse, J. Moncel, M. Montassier, R. Naserasr, A. Parreau, A. Pêcher, A. Raspaud, R. Razafindramanana, E. Sopena, L.D. Tong, P. Valicov.

*Wednesday*

- 11h-15h:
*Matjaz Kovse - On identification using paths and related problems*

Definition of subgraphs-identification, debate about some related problems, exact value of path identifying number for paths, cycles and bounds for trees.

- 15h35-17h00:
*Eleonora Guerrini - Hypercubes and identification problems*

Known bounds for r-identifying codes in hypercubes, a construction to r-identify hypercubes, similar condition for weak identification, another construction for light identification of hypercubes.

- 17h00-18h00: open problems: the identifying codes polynomial by R.Naserasr.

*Thursday*

- 10h-11h:
*Aline Parreau - Coloring graphs to distinguish (adjacent) vertices*

Definition of distinguishing colorings: edge coloring, vertex coloring and edge + vertex coloring. Adjacent Vertices Distinguishing (AVD) by vertex coloring for paths, trees, bipartite graphs (with 4 colors). NP-completeness of deciding if a bipartite graph is 3 AVD-colorable. 2k+1 AVD-coloring of k-trees (tight upper bound, reached for the kth power of paths on 2k+2 vertices). Conjecture that twice the chromatic number is an AVD upper bound for chordal graphs, not true in general graphs. AVD coloring of split graphs in terms of the size of a minimum separating set, gives an AVD-coloring on 2k colors, longer proof allows 2k-1.

- 11h-12h + 14h-15h:
*Olivier Delmas - Some variations of identifying codes*

Definitions of Weak codes and light codes. Some general bounds and values for cycles. Relationship between all definitions and a generalized definition.

- 15h-17h:
*Open discussion about the IDEA project*

Discussion on work done and to be done.

*Friday*

- 10h-11h:
*Petru Valicov - Identifying codes in Hypercubes and projective cubes*

Recall a conjecture on the doubling of the value of IC in the hypercubes (HC) of two consecutive dimensions and why it can't be solved trivially. Definition of the projective cube (PC). Questions and ideas about the relationship between minimum ICs in the HC and the PC.

- 11h-12h:
*Reza Naserasr - Different proofs of Bondy's theorem and identifying codes of directed graphs*

5 different proofs of Bondy's theorem on induced subsets using graph theory or linear algebra. Some other results of Lovasz's book.

- 14h-15h:
*Florent Foucaud - Extremal cardinalities of identifying codes*

Characterizing graphs on n vertices having minimum IC n-1, and digraphs having minimum IC n. An application to Bondy's theorem.