Journal of the Korean Society for Industrial and Applied Mathematics
( Vol.11 NO.4 / 2007 )
Applications of Graph Theory(ENG)
S. Pirzada ,Ashay Dharwadker 
19-38 Page
1. The Cantor-Schroder-Bernstein Theorem
2. Fermat's(litte) Theorem
3. The Nielson-Schreier Theroem
4. The Snp Assembly Problem
5. Computer Network Security
6. The Timetabling Problem
7. Map Coloring and Gsm Mobile Phone Networks
8. Knight's Tours
Own Status
Graph theory is becoming increasingly significant as it is applied
to other areas of mathematics, science and technology. It is being
actively used in fields as varied as biochemistry (genomics),
electrical engineering (communication networks and coding theory),
computer science (algorithms and computation) and operations
research (scheduling). The powerful combinatorial methods found in
graph theory have also been used to prove fundamental results in
other areas of pure mathematics. This paper, besides giving a
general outlook of these facts, includes new graph theoretical
proofs of Fermat's Little Theorem and the Nielson-Schreier Theorem.
New applications to DNA sequencing (the SNP assemble problem) and
computer network security (worm propagation) using minimum vertex
covers in graphs are discussed. We also show how to apply edge
coloring and matching in graphs for scheduling (the timetabling
problem) and vertex coloring in graphs for map coloring and the
assignment of frequencies in GSM mobile phone networks. Finally, we
revisit the classical problem of finding re-entrant knight's tours
on a chessboard using Hamiltonian circuits in graphs.