Graph Theory Applications in Network Security

Project Report from the year 2015 in the subject Computer Science - IT-Security, Central Queensland University (Theory Lab), language: English, abstract: Graph theory has become a very critical component in many applications in the computing field including networking and security. Unfortunately, it is also amongst the most complex topics to understand and apply.

In this paper, we review some of the key applications of graph theory in network security. We first cover some algorithmic aspects, then present network coding and its relation to routing.

The rapid growth in Global mobile communication networks demands new solutions for existing problems. Such problems include reduced bandwidth in mobile devices and the constant change in their associated network topologies. This creates a need for network algorithms with:

1. least possible communication traffic

2. High speed execution.

The two challenges can be overcome by application of graph theory in developing local algorithms (Algorithms that require low rounds of communication). In this paper we explore applications of graph theory in cellular networks with an emphasis on the 'four-color' theorem and network coding and their relevant applications in wireless mobile networks.