Multicoloring of graphs to secure a secret

Vojković, Tanja; Vukičević, Damir; Zlatić, Vinko (2018) Multicoloring of graphs to secure a secret. Rad Hrvatske akademije znanosti i umjetnosti. Razred za matematičke, fizičke i kemijske znanosti. Matematičke znanosti, 22 (534). pp. 1-22. ISSN 1845-4100

Preview

PDF - Accepted Version - article Download (262kB) | Preview

Abstract

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.

Item Type:	Article
Additional Information:	Partial support of the Croatian Ministry of Science and Education is gratefully acknowledged. We acknowledge the Israel-Italian collaborative project NECST as well as support by the H2020 CSA Twinning project No. 692194.
Uncontrolled Keywords:	Graph theory ; graph coloring ; multicoloring ; secret sharing
Subjects:	NATURAL SCIENCES > Mathematics NATURAL SCIENCES > Mathematics > Discrete and Combinatorial Mathematics
Divisions:	Theoretical Physics Division
Projects:	Project title Project leader Project code Project type Ruđer Bošković Institute: Twinning for a step forward of the Theoretical Physics Division-RBI-T-WINNING Fabrizio NESTI 692194 EK
Depositing User:	Vinko Zlatić
Date Deposited:	29 Apr 2020 11:44
URI:	http://fulir.irb.hr/id/eprint/5468
DOI:	10.21857/m3v76t6jky

Actions (login required)

View Item