Rainbow connections of graphs

This new concept comes from the communication of information between agencies of  government. The Department of Homeland Security of USA was created in 2003 in response to the weaknesses discovered in the transfer of classified information after the September 11, 2001 terrorist attacks. Ericksen made the following observation: An unanticipated aftermath of those deadly attacks was the realization that law enforcement and intelligence agencies couldn't communicate with each other through their regular channels, from radio systems to databases. The technologies utilized were separate entities and prohibited shared access, meaning that there was no way for officers and agents to cross check information between various organizations.

While the information needs to be protected since it relates to national security, there must also be procedures that permit access between appropriate parties. This two-fold issue can be addressed by assigning information transfer paths between agencies which may have other agencies as intermediaries while requiring a large enough number of passwords and firewalls that is prohibitive to intruders, yet small enough to manage (that is, enough so that one or more paths between every pair of agencies have no password repeated). An immediate question arises: What is the minimum number of passwords or firewalls needed that allows one or more secure paths between every two agencies so that the passwords along each path are distinct?


1- Rainbow Connections of Graphs: A Survey, Graphs and CombinatoricsJanuary 2013, Volume 29, Issue 1, pp 1-38

2- A matter of security, Graduating Engineer & Computer Careers (2007),

3-Rainbow connection in graphs, Mathematica Bohemica 133 (1).

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *