Izvorni znanstveni članak
https://doi.org/10.21857/m3v76t6jky
Multicoloring of graphs to secure a secret
Tanja Vojković
orcid.org/0000-0002-8160-7757
; Department of Mathematics, Faculty of Science, University of Split, 21000 Split, Croatia
Damir Vukičević
; Department of Mathematics, Faculty of Science, University of Split, 21000 Split, Croatia
Vinko Zlatić
; Institut Ruđer Bošković, 10 000 Zagreb, Croatia
Sažetak
Vertex coloring and multicoloring of graphs are a well known subject in graph theory, as well as their applications. In vertex multicoloring, each vertex is assigned some subset of a given set of colors. Here we propose a new kind of vertex multicoloring, motivated by the situation of sharing a secret and securing it from the actions of some number of attackers. We name the multicoloring a highly a-resistant vertex k-multicoloring, where a is the number of the attackers, and k the number of colors. For small values a we determine what is the minimal number of vertices a graph must have in order to allow such a coloring, and what is the minimal number of colors needed.
Ključne riječi
Graph theory; graph coloring; multicoloring; secret sharing
Hrčak ID:
206192
URI
Datum izdavanja:
28.9.2018.
Posjeta: 955 *