Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5776898 | Discrete Mathematics | 2017 | 11 Pages |
Abstract
In 1998, Karpovsky, Chakrabarty and Levitin introduced identifying codes to model fault diagnosis in multiprocessor systems (Karpovsky et al., 1998). In these codes, each vertex is identified by the vertices belonging to the code in its neighborhood. There exists a coloring variant as follows: a globally identifying coloring of a graph is a coloring such that each vertex is identified by the colors in its neighborhood. We aim at finding the maximum length of a cycle with such a coloring, given a fixed number of colors we can use. Parreau (2012) used Jackson's work (Jackson, 1993) on universal cycles to give a lower bound of this length. In this article, we will adapt what Jackson did, to improve this result.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Pierre Coupechoux,