Sylvain Gravier
Identifying codes in line graphs.
Mon, 07/04/2011 - 15:01 — SomNambulAuthors: Sylvain Gravier, Aline Parreau, Florent Foucaud, Reza Naserasr, Petru Valicov
Subjects: Combinatorics
AbstractAn identifying code of a graph is a subset of its vertices such that every
vertex of the graph is uniquely identified by the set of its neighbours within
the code. We study the edge-identifying code problem, i.e. the identifying code
problem in line graphs. If $\ID(G)$ denotes the size of a minimum identifying
code of an identifiable graph $G$, we show that the usual bound $\ID(G)\ge
\lceil\log_2(n+1)\rceil$, where $n$ denotes the order of $G$, can be improved
to $\Theta(\sqrt{n})$ in the class of line graphs. Moreover, this bound is
tight.On two variations of identifying codes.
Mon, 04/26/2010 - 15:01 — SomNambulAuthors: Olivier Delmas, Sylvain Gravier, Mickael Montassier, Aline Parreau
Subjects: Discrete Mathematics
AbstractIdentifying codes have been introduced in 1998 to model fault-detection in
multiprocessor systems. In this paper, we introduce two variations of
identifying codes: weak codes and light codes. They correspond to
fault-detection by successive rounds. We give exact bounds for those two
definitions for the family of cycles.
User login
